By

Contents
  1. 1. 题目
  2. 2. 解题思路
    1. 2.1. 思路1
    2. 2.2. 思路2

题目

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2：
输入: “cbbd”
输出: “bb”
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

思路1

题目两个部分，一个部分是找到子串，一个是子串是回文
会问用双指针判断
通过找到重复字符，来排查子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
    public String longestPalindrome(String s) {
        if(s.equals(""))return s;
        Map<Character,List<Integer>> map = new HashMap<>();
        char[] array = s.toCharArray();
        Integer ans = 0;
        String result = "";
        
        for(int i = 0 ; i< array.length; i++){
            char one = array[i];
            if(!map.containsKey(one)){
                List<Integer> list = new ArrayList<Integer>();
                list.add(i);
                map.put(one,list);
            }else{
                List<Integer> list = map.get(one);
                //System.out.println("one:"+one);
                for(int j = 0 ; j< list.size() ; j++){
                    Integer num = list.get(j);
                    //System.out.println("num:"+num);
                    if(palindrome(array,num,i)){
                        if(i - num +1 > ans){
                            ans = i - num +1;
                            result = s.substring(num,i+1);
                        }
                    }
                }
                list.add(i);
            }
        }
        if(result.equals("")){
            return s.substring(0,1);
        }
        return result;
    }
public boolean palindrome(char[] array,int start,int end){
        int i = start;
        int j = end;
        boolean state = true;
        while(i < j){
            if(array[i]!= array[j]){
                state = false;
                //System.out.println(i+":"+j);
                break;
                
            }
            i++;
            j--;
        }
        return state;
    }
}

暴力法，103个测试用例，通过了102个，aaaaaaaaaaaaaaaaaa这个超时

思路2

看参考答案
中心对称法
只有2n-1个中心，aba，abba
从中心扩展

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public String longestPalindrome(String s) {
        if(s.equals(""))return s;
        char[] array = s.toCharArray();
        int start = 0; int end = 0;
        for(int i = 0 ; i< s.length() ; i++){
            int length1 = center(array, i, i);
            int length2 = center(array, i, i+1);
            int length = Math.max(length1,length2);
            if(length > end - start +1){
                start = i - (length - 1) /2;
                end = i + (length /2);
            }
        }
        return s.substring(start,end+1);
    }
    private int center(char[] array , int left ,int right){
        int L = left;int R = right;
        while(L >= 0 && R< array.length && array[L] == array[R]){
            L--;
            R++;
        }
        return R-L - 1;
    }
}

Contents
  1. 1. 题目
  2. 2. 解题思路
    1. 2.1. 思路1
    2. 2.2. 思路2