5. Longest Palindromic Substring（最长回文子串）

5. Longest Palindromic Substring

1 2	Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

1
2
3

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

1 2	Input: "cbbd" Output: "bb"

解法一：枚举 + 贪心

枚举出所有子串，判断其是不是回文串，我们可以从最长的子串开始枚举，如果发现是回文串，就可以立马返回。

bool isPalindrome(string s) {
  int len = s.size();
  for (int i = 0; i < len; i++) {
    if (s[i] != s[len - i - 1]) return false;
  }
  return true;
}

string longestPalindrome(string s) {
  int len = s.size();
  if (len < 2) return s;
  for (int i = 0; i < len; i++) {
    for (int j = 0; j <= i; j++) {
      string str1 = s.substr(j, len - i);
      if (isPalindrome(str1)) {
        return str1;
      }
    }
  }
  return s.substr(0, 1);
}

这样做的结果就是时间复杂度几乎高达O(n^3)，只能过部分数据。

所以可以改进一下：
在上面的代码中我们每次都调用了substr方法，其实可以不用真的构造出一个子串，接下来我们改造一下 isPalindrome 函数

bool isPalindrome(string &s, int start, int end) {
  for (int i = start; i <= end; i++) {
    if (s[i] != s[end - i + start]) return false;
  }
  return true;
}

string longestPalindrome(string s) {
  int len = s.size();
  if (len < 2) return s;
  for (int i = 0; i < len; i++) {
    for (int j = 0; j <= i; j++) {
      if (isPalindrome(s, j, j + len - i - 1)) {
        return s.substr(j, len - i);
      }
    }
  }
  return s.substr(0, 1);
}

经过这个优化之后，试了一下，可以通过。

能不能再快一点？

解法二：动态规划 O(n^2)

dp[i][j] = 1 表示子串s[i…j]是回文串；

那么当s[i - 1] == s[j + 1]，则dp[i - 1][j + 1]也是回文串；

i代表子串长度，j代表子串头部的位置;

我们从小到大枚举子串，当判断较长的子串s[j…i]时，

只需要判断首尾是否相等，如果相等且dp[j + 1][j + i - 1 - 1] == 1，那么就可以得出 dp[j][j + i - 1] = 1;

这样，当枚举完所有子串时，就能得出最长回文子串的长度啦

string longestPalindrome(string s) {
  if (s.size() < 2) return s;
  int len = s.size();
  int dp[len][len];
  dp[0][0] = 1;
  for (int i = 1; i < len; i++) {
    dp[i][i - 1] = dp[i][i] = 1; // dp[i][i - 1] = 1的是为了处理长度为2的情况
  }
  int start = 0, maxLen = 0;
  for (int i = 2; i <= len; i++) {
    for (int j = 0; j <= len - i; j++) {
      if (s[j] == s[j + i - 1] && dp[j + 1][j + i - 2]) {
        dp[j][j + i - 1] = 1;
        if (i > maxLen) {
          maxLen = i;
          start = j;
        }
      }
    }
  }
  return s.substr(start, maxLen);
}

5. Longest Palindromic Substring

解法一： 枚举 + 贪心

解法二：动态规划 O(n^2)

解法一：枚举 + 贪心