5. 最长回文子串

这是LeetCode热题100的第5题 5.最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

1
2
3
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

1
2
输入：s = "cbbd"
输出："bb"

提示：

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成

解法

暴力做法

枚举所有的子串，如果是回文并且长度大于答案，那么更新答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    private boolean good(String s, int i, int j) {
        for (int l = i, r = j; l < r; l++, r--) {
            if (s.charAt(l) != s.charAt(r)) return false;
        }
        return true;
    }
    public String longestPalindrome(String s) {
        int n = s.length();
        int st = 0, ed = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (good(s, i, j) && (j - i > ed - st)) {
                    st = i;
                    ed = j;
                }
            }
        }

        return s.substring(st, ed + 1);
    }
}

动态规划

如果一个串是回文串，那么它去掉头部和去掉尾部后也是回文串，可以通过这个特点递推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        String res = "";
        int ans = 0;
        boolean[][] f = new boolean[n][n];
        for (int i = 1; i <= n; i++) {
            for (int l = 0; l < n; l++) {
                int r = l + i - 1;
                if (r >= n) break;
                f[l][r] = ((i == 1) || (i == 2) || f[l + 1][r - 1]) && (s.charAt(l) == s.charAt(r));
                if (f[l][r] && i > ans) {
                    res = s.substring(l, r + 1);
                    ans = i;
                }
            }
        }

        return res;
    }
}

中心扩展

从单个字符或者两个字符开始扩展，然后更新答案

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
class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        String res = "";
        for (int i = 0; i < n; i++) {
            int l = i, r = i;
            while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
                l--;
                r++;
            }
            //  aabcdbdcea
            //  012345678
            if (r - l - 1 > res.length()) res = s.substring(l + 1, r);

            l = i;
            r = i + 1;
            while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
                l--;
                r++;
            }
            if (r - l - 1 > res.length()) res = s.substring(l + 1, r);
        }

        return res;
    }
}