【LeetCode-5】最长回文子串

问题

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

示例

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

解答：动态规划

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size(), maxLen = 0, start = 0;
        bool dp[n][n]; memset(dp, 0, sizeof(dp));
        for (int j = 0; j < n; j++) { // 结束位置
            for (int i = 0; i <= j; i++) { // 起始位置
                if (s[i] == s[j]) {
                    if (j - i < 3) dp[i][j] = 1;
                    else dp[i][j] = dp[i + 1][j - 1];
                    if ((j - i + 1 > maxLen) && dp[i][j]) {
                        maxLen = j - i + 1;
                        start = i;
                    }
                }
            }
        }
        return s.substr(start, maxLen);
    }
};

重点思路

使用dp[i][j]描述以i为起点，j为终点的字符串是否为回文串。很容易想到dp[i][j]与dp[i-1][j-1]有关系，可以依此写出状态转移方程。

这里特别要注意二维动态规划的顺序，即外层循环代表起始位置还是结束位置。我们一定要保证状态转移方程中右边式子中的变量已经被处理过。

【LeetCode-5】最长回文子串

原文：https://www.cnblogs.com/tmpUser/p/14504839.html