Leetcode 5. 最长回文字串

请注意,本文编写于 1474 天前,最后修改于 1474 天前,其中某些信息可能已经过时。

题目

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

示例 1:

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

示例 2:

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

思路

通过动态规划来解,设字符串为str,设二维数组dpi,表示str[i]到str[j]的子串是否为回文字串,并用pre,last作为标记,保存已找到的最长的回文字串。并且,只要当dpi-1为true,那么只要str[i]==str[j]即可,特殊情况有i=j+1,需要考虑。

代码

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.length()==0) {
            return "";
        }
        int n = s.length();
        bool dp[n][n];
        int pre = 0, last = 0;
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
            for (int j = i-1; j >= 0; j--) {
                dp[i][j] = (s[i] == s[j]) && (i-j==1 || dp[i-1][j+1]);
                if (dp[i][j] && (i-j)>(last-pre)) {
                    last = i;
                    pre = j;
                }
            }
        }
        return s.substr(pre, last-pre+1);
    }
};

此处评论已关闭