leetcode5

今天这道题我可是真的佛了，绝对是网站的问题，而不是我写错了，最长回文串居然是a，反正我是看傻了，不管了先把自己的思想记录下来。

以下是题目

5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"

思路：
1、用map<Integer, List>，这样就可以记录每个字母出现的位置，例如a{1，3，5，6，7}表示a出现再这些位置上，而且字符串遍历一次添加字母所在位置的话，List内的数字索引是有序的。

2、将map中的所有list遍历，取每个list内最小（第一个）数字和最大（最后一个）数字，然后相减得出长度，然后进行比较。从而得出最长的回文字符串

3、注意String.substring(start,end)的方法，end是最后end-1位置的字符，总长度为end-start。故最后end得加1

  public String longestPalindrome(String s) {
         
         int count = 0;
         int start=0,end=0;
         
         HashMap<Character,List> map = new HashMap<>();
         for(int i = 0; i < s.length(); i++)//记录字符出现的位置
         {
             char temp = s.charAt(i);
             if(map.containsKey(temp)) {//如果字符之前出现过，则将其现在的索引添加到list中，然后更新map
                ArrayList<Integer> A =  (ArrayList<Integer>) map.get(temp);
                A.add(i);
                map.replace(temp, A);
             }
             else {
                 ArrayList<Integer> B =  new ArrayList<Integer>();//如果字符没有出现过，则将其字符和索引加入map
                 B.add(i);
                 map.put(temp, B);
             }
                 
         }
         
         for(Map.Entry entry : map.entrySet()) {//遍历map，找出最大的字符索引间差值，其就是回文所在的索引开头结尾的位置
             ArrayList<Integer> C = (ArrayList<Integer>) entry.getValue();
             int len = C.get(C.size()-1)-C.get(0)+1;
             if(len>count) {
                 count = len;
                 start = C.get(0);//回文的开头
                 end = C.get(C.size()-1)+1;//回文的结尾，因为substring的方法end比较特别，所以end需加1
                 }
         }
         
         String sub = s.substring(start, end);
         return sub;
        
    }

输入babad，

输出aba而不是bab，

其原因是因为hashmap的遍历会自动给你的key进行排序，而不是按照放入的顺序进行放出。