【Leetcode】5.最长回文子串

5. 最长回文子串

题目

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

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

示例 2：
输入: "cbbd"
输出: "bb"

方法1（动态规划）

一个长度大于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;

    }
}

方法2（中心扩展法）

假设字符串的长度为N，那么回文串可能的中心有2N-1种。其中，每个单字符串都可作为回文串的中心，这种情况有N种。其次，双字符串也可作为回文串的中心，这种情况有N-1种。单字符中心负责扩展成长度为奇数的字符串，双字符串中心可以扩展成长度为偶数的字符串。例如：

  • 字符串“aba”有5种可能的中心：a、b、c、ab、ba
  • 字符串“abba”有7种可能的中心：a、b、b、a、ab、bb、ba

中心扩展法的基本思想为：对于每一个中心都计算一次以其为中心的最长回文串长度

具体算法：对于每一个可能的回文中心，都尽可能地扩展它对应的回文区间[left, right]，直到left<0或者right>=N或者S[left]不等于S[right]为止

代码

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

本题的中心扩展法思路与647 回文子串一致

时间复杂度：$O(n^2)$（对于每一个可能的中心都要遍历一次字符串）
空间复杂度：O(1)