Leetcode.5 最长回文子串

题目链接

Leetcode.5 最长回文子串

题目描述

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

如果字符串的反序与原始字符串相同则该字符串称为回文字符串。

示例 1

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

示例 2

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

提示

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

分析

本题可以使用 区间DP 求解。我们设 $f(i,j)$ 代表 $s$ 的下标 $i$ 到 下标 $j$ 的一段子字符串是否为回文串。

我们在判断回文串的时候设置两个变量 最长回文子串的长度len 和 最长回文子串的起始下标idx。遍历的过程中不断地更新这两个变量遍历结束时的 len 就是最长回文子串的长度idx就是最长回文子串的起始下标。

最后用 substring 截取子串的方法返回即可。

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

C++代码

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();

        bool f[n][n];
        memset(f,false,sizeof f);

        int len = 0,idx = -1;
        for(int i = n - 1;i >= 0;i--){
            for(int j = i;j < n;j++){
                if(s[i] == s[j]){
                    if(j - i <= 1) f[i][j] = true;
                    else if(f[i+1][j-1]) f[i][j] = true;

                    if(f[i][j] && j-i+1 > len){
                        len = j - i + 1;
                        idx = i;
                    }
                }
            }
        }
        return s.substr(idx,len);
    }
};

Java代码:

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();

        boolean [][] f = new boolean[n][n];
        //记录最长回文子串的长度 和 起始位置
        int len = 0,idx = -1;
        for(int i = n - 1;i >= 0;i--){
            for(int j = i;j < n;j++){
                if(s.charAt(i) == s.charAt(j)){
                    // 特殊情况 i == j i 和 j都指向了同一个字符一个字符也是回文串
                    //j - i == 1类似 "aa" 这样的情况也是回文串
                    if(j - i <= 1) f[i][j] = true;
                    // "a bbb....b a" 此时 s[i] == s[j] 所以我们还要判断中间的那一段是否为回文串 即 f[i+1][j-1]
                    else if(f[i+1][j-1]) f[i][j] = true;
                    //当 i ~ j这一段子串是回文串的情况 并且 这段长度 大于 len 才更新最大长度 和 起始下标
                    if(f[i][j] && j - i + 1 > len){
                        len = j - i + 1;
                        idx = i;
                    }
                }
            }
        }
        return s.substring(idx,idx+len);
    }
}