LeetCode-5 最长回文子串

LeetCode-5 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

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

示例 2：

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

提示：

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

采用动态规划的思想

首先单个字母一定是回文串，其次判断长度为2的回文串，然后判断长度大于等于3的回文串

创建数组dp使得dp[i][j]=1表示i~j为一个回文串，易知当dp[i][j]=1时若存在s[i-1]=s[j+1]则dp[i-1][j+1]=1

所以存在状态转移方程 iff s[i]==s[j]&&dp[i+1][j-1]==1 then dp[i][j]=1

#include <string>
#include <iostream>
#include <vector>

using namespace std;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    string longestPalindrome(string s) {
        cout << s << endl;
        int l = s.length();
        if (l <= 1) {
            return s;
        } else if (l == 2) {
            if (s[0] != s[1]) {
                return s.substr(0, 1);
            } else {
                return s;
            }
        } else {
            vector<vector<int> > dp(l, vector<int>(l));
            string str = s.substr(0, 1);
            for (int i = 0; i < l; ++i) {
                dp[i][i] = 1;
                if (i + 1 < l && s[i] == s[i + 1]) {
                    dp[i][i + 1] = 1;
                    str = s.substr(i, 2);
                }
            }
            for (int len = 3; len <= l; len++)
            {
                for (int i = 0; i + len - 1 < l; i++) {
                    int j = len + i - 1;
                    if (s[i] == s[j] && dp[i + 1][j - 1] == 1)
                    {
                        dp[i][j] = 1;
                        str = s.substr(i, len);
                    }
                }
            }
            cout << str << endl;
            return str;
        }
    }
};
//leetcode submit region end(Prohibit modification and deletion)

int main() {
    Solution s;
    s.longestPalindrome("aacabdkacaa");
}