5. 最长回文子串

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

示例 1:

输入:s = “babad”
输出:“bab”
解释:“aba” 同样是符合题意的答案。

示例 2:

输入:s = “cbbd”
输出:“bb”

提示:

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

算法思路:

解法一:动态规划,和题目【647. 回文子串】类似,dp[i][j] 表示 区间为 [i,j] 的子串是否是回文串,递推公式如下:

  • 比较 s[i]]s[j]i <= j):

    • 如果不相等,则说明不是回文串
    • 如果相等,分以下情况:
      • j == i:单独一个字符是回文串
      • j == i+1:形如 aa 是回文串
      • 否则,比如:cbabc 则看 bab,即为 dp[i + 1][j - 1]

并通过记录两个变量 start、len,每次判断符合(dp[i][j] 为 true 且 j - i + 1 > len ),则进行更新。

时间复杂度:O(N^2)

空间复杂度:O(N^2)

解法二:采用 双指针 ,通过中心串然后同时向两边扩散看是不是对称,需要注意的是中心串有两种情况,即长度为 1 和长度 为 2:

  • 长度为 1 的则分别扩散为 长度为 3、5、7…
  • 长度为 2 的则分别扩散为 长度为 4、6、8…

时间复杂度:O(N^2)

空间复杂度:O(1)

代码实现:

动态规划:

class Solution {
    public String longestPalindrome(String s) {
        return dpFn(s);
    }
    // dp
    public String dpFn(String s) {
        if (s == null || s.length() == 0) return s;
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int start = 0, len = 1;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) != s.charAt(j)) {
                    dp[i][j] = false;
                } else {
                    if (j - i <= 1) {
                        dp[i][j] = true;
                        // 满足则更新
                        if (j - i + 1 > len) {
                            start = i;
                            len = j - i + 1;
                        }
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                        if (dp[i][j]) {
                            // 满足则更新
                            if (j - i + 1 > len) {
                                start = i;
                                len = j - i + 1;
                            }
                        }
                    }
                }
            }
        }
        return s.substring(start, start + len);
    }
}

双指针:

class Solution {
    public String longestPalindrome(String s) {
        return doubleIndex(s);
    }

    private int left = 0, maxLength = 1;
    // 双指针
    public String doubleIndex(String s) {
        int n = s.length();
        for (int i = 0; i < n; i++) {
            // 长度为 1,扩散后对应长度为奇数
            expand(s, i, i, n);
            // 长度为 2,扩散后对应长度为偶数
            expand(s, i, i + 1, n);
        }
        return s.substring(left, left + maxLength);
    }

    public void expand(String s, int i, int j, int n) {
        while (i >= 0 && j < n && s.charAt(i) == s.charAt(j)) {
            if (j - i + 1 > maxLength) {
                left = i;
                maxLength = j - i + 1;
            }
            i--;
            j++;
        }
    }
}

Q.E.D.


以无限为有限,以无法为有法