5. 最长回文子串

5. 最长回文子串

动态规划

状态转移条件容易错 j - i <= 1 || dp[i + 1][j - 1]。

当字符 i 和 字符 j 相等时

1. i 和 j 相邻：j - i <= 1
2. i 和 j 不相邻：dp[i + 1][j - 1] == true

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for(int i = 0; i < n; i++) dp[i][i] = true;
        int start = 0, end = 0, len = 0;

        for(int i = n - 1; i >= 0; i--){
            for(int j = i + 1; j < n; j++){
                if(s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i + 1][j - 1])){
                    dp[i][j] = true;
                    if(len < j - i + 1){
                        len = j - i + 1;
                        start = i;
                        end = j;
                    }
                }
            }
        }

        return s.substring(start, end + 1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

中心扩展法

class Solution {
    public String longestPalindrome(String s) {
        String res = "";
        for(int i = 0; i < s.length(); i++){
            String str1 = findLongest(s, i, i + 1);
            String str2 = findLongest(s, i, i);
            res = res.length() > str1.length() ? res : str1;
            res = res.length() > str2.length() ? res : str2;
        }
        return res;
    }

    private String findLongest(String s, int l, int r){
        while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
            l--;
            r++;
        }
        return s.substring(l + 1, r);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20