5.最长回文子串.md

5.最长回文子串

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

 

示例 1：

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

示例 2：

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

 

提示：

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

标签：

['字符串', '动态规划']

难度：Medium

喜欢：5524

---

暴力枚举

(暴力枚举)

1. 枚举每一个字符串 $[i, j]$
2. 判断 $[i,j]$是否是回文串

时间复杂度 $O(n^3)$

枚举字符串 $O(n^2)$

判断回文串 $O(n)$

总时间复杂度 ：相乘 得 $O(n^3)$

代码实现

参考文献

动态规划

(记忆化搜索)

$f[i, j]$ 表示 $[i, j]$ 是否为 回文串

搜索过程中，更新最长子串长度

时间复杂度 $O(n^2)$

代码实现

class Solution {
    public String longestPalindrome(String s) {
        char[] sc = s.toCharArray();
        int n = s.length();
        String res = "";
        if (n == 0) return res;
        boolean f[][] = new boolean[n][n];
        for (int len = 1; len <=n ; len++) {
            for (int i=0, j; (j = i+len-1) < n; i++){
                if (len == 1) f[i][j] = true;
                else if (len == 2 && sc[i] == sc[j]) f[i][j] = true;
                else {
                    f[i][j] = sc[i] == sc[j] && f[i+1][j-1];
                }
                if (f[i][j] && res.length() < len) {
                    res = s.substring(i, j + 1);
                }
            }
        }
        return res;
    }
}

参考文献

中心扩展法

(枚举回文串的中心) $O(n^2)$

从中心向两边扩展

时间复杂度

枚举每一个中心时间复杂度 $O(n)$

向两边扩展 $O(n)$

总共： $O(n^2)$

代码实现

参考文献

相似题目

516.最长回文子序列