leetCode 5. 最长回文子串

题目描述

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

示例 1：

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

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

思考

首先想到的肯定是暴力解法，枚举出所有的子串，判断子串是不是回文串，然后找到最长的回文串。这种方法时间复杂度太高，放弃
然后想到的是动态规划（DP），其实这是一道标准的考动态规划的题（当然除了动态规划有更优秀的解法，做完看了下大神们的解题都用Manacher）
可能很多人看到要是用动态规划来解题，就觉得很头疼，不知道如何下手
其实动态规划是一个很简单的算法，用通俗的话来讲就是把整个过程分解为若干个小问题去解决

在这题里，判断一个回文串，长度小于等于3的时候，我们只需要判断首位和末尾是否是回文传就可以了；当子串长度超过4的时候，我们就要多次进行判断。

我们用一个二维数组 dp[i][j] 来存储子串下标从i-j是否是回文串
所以就会有两种判断的方式

if (i - 2 <= j) {
  dp[j][i] = s[i] == s[j];
} else {
  dp[j][i] = (s[i] == s[j] && dp[j + 1][i - 1]);
}

用两个for循环遍历之后，我们就构建了一个dp图

for (int i = 0; i < s.size(); i++) {

  for (int j = 0; j < i; j++) {
    if (i - 2 <= j) {
      dp[i][j] = s[i] == s[j];
  } else {
    dp[i][j] = (s[i] == s[j] && dp[i-1][j+1]);
  }
}

然后遍历一遍这张dp图，我们就可以得到我们想要的结果
使用startIndex来记录最长回文串的起点，maxLength来记录最长回文串的长度
这个过程，也可以放在构建dp图的时候同时进行

for (int i = 0; i < s.size(); i++) {
  for (int j = 0; j < i; j++) {
    if ((maxLength < i - j + 1) && dp[i][j]) {
      maxLength = i - j + 1;
      startIndex = j;
    }
  }
}

代码

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.size() == 0) {
            return "";
        }
        bool dp[s.size()][s.size()];

        int startIndex = 0;
        int maxLength = 1;
        for (int i = 0; i < s.size(); i++) {

            for (int j = 0; j < i; j++) {
                if (i - 2 <= j) {
                    dp[i][j] = s[i] == s[j];
                } else {
                    dp[i][j] = (s[i] == s[j] && dp[i-1][j+1]);
                }

                if ((maxLength < i - j + 1) && dp[i][j]) {
                    maxLength = i - j + 1;
                    startIndex = j;
                }
            }
        }
        return s.substr(startIndex, maxLength);
    }
};