【Leetcode】5.最长回文子串

5 最长回文子串

题目

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。


示例 2：

输入: "cbbd"
输出: "bb"

方法一（动态规划）

一个长度大于2的回文串，去掉首尾两个字母后仍然是一个回文串。
用dp[i][j]表示字符串s的第i到j个字母组成的串是否为回文串。即有动态规划状态转移方程

1
dp[i][j] = dp[i+1][j-1] && s.charAt(i) == s.charAt(j)

意为：如果从i+1到j-1的一个子串是回文串，并且s[i]和s[j]相等，则从i到j的子串也是回文串
接下来考虑边界条件：（回文串长度小于等于2时）

  • s长度为1：肯定为回文串
  • s长度为2：判断s[i]和s[j]是否相等

由于在状态转移方程中，我们是从长度较短的字符串向长度较长的字符串进行转移的，所以要先遍历j，再遍历i。在遍历的过程中不断更新max_len，即可获得最长回文子串长度j-i+1和起始位置start。

代码： 

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
class Solution {
    public String longestPalindrome(String s) {
        if(s == null || s.length() < 1)
            return "";
        int length = s.length();
        //dp[i][j]表示字符串s的第i到j个字母组成的串是否为回文串
        boolean[][] dp = new boolean[length][length];
        int start = 0;
        //max_len记录最长回文子串的长度
        int max_len = 1;
        for(int j = 0; j < length; j++){
            for(int i = 0; i < length; i++){
                //i必须小于j，因此当i大于j时可以直接continue跳过不处理
                if(i > j)
                    continue;
                //长度为1的子串肯定是回文串
                if(i == j)
                    dp[i][j] = true;
                //子串长度为2并且i和j对应的字符相等时，为回文字符串
                if(j == i + 1){
                    dp[i][j] = s.charAt(i) == s.charAt(j);
                }
                //子串长度大于2时，依据动态规划的状态转移方程判断
                if(j - i > 1){
                    dp[i][j] = dp[i+1][j-1] && s.charAt(i) == s.charAt(j);
                }
                //更新回文子串的最长长度max_len以及这个子串的起始位置start
                if(dp[i][j] && j-i+1 > max_len){
                    max_len = j-i+1;
                    start = i;
                } 
            }
        }
        String res = new String(s.toCharArray(), start, max_len);
        return res;

    }
}

注：方法toCharArray()将s转换为一个字符数组，该字符数组中存放了当前字符串中的所有char类型字符。

方法二（中心扩展法）

字符串s可能有2N - 1个可能的中心，其中：

  • 每个单字符都可能作为中心扩展出长度为奇数的回文串，这种情况有N种。
  • 每一对相邻的双字符也可能作为中心扩展出长度为偶数的回文串，这种情况有N - 1种

对每一个中心都尽可能地尝试向外扩展，找到能扩出的最长长度以及其对应的最长回文串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public String longestPalindrome(String s) {
    if(s == null || s.length() == 0)
        return "";
    int maxLen = 0;
    int res_left = 0;
    int res_right = 0;
    for(int i = 0; i < 2 * s.length() - 1; i++){
        int left = i / 2;
        int right = i / 2 + i % 2;
        while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
            left--;
            right++;
        }
        int len = right - left - 1;
        if(len > maxLen){
            maxLen = len;
            res_left = left + 1;
            res_right = right - 1;
        }
    }
    return s.substring(res_left, res_right + 1);
}