5. Longest Palindromic Substring

发表于 | 分类于

每日一题 2019 - 03 - 02

题目:

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"

解法：

这个题让我们求出给定串中的最长回文串序列，思路大概如下：

  • 如果一个串是回文串，那么这个串开头与结尾各去掉一个字符之后仍是回文串
  • 在扩充字符串长度时候，要保证一次最多增加两个字符

有了上面的思路，我们就可以从头开始遍历寻找最长回文序列，DP[size][size]定义为动态规划的记录点，也即DP[i][j]代表从长度为i到j的串是回文串。

另解：

Manacher算法

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    string longestPalindrome(string s) {
        int dp[s.size()][s.size()] = {0}, left = 0, right = 0, len = 0;
        for (int i = 0; i < s.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                dp[j][i] = (s[i] == s[j] && (i - j < 2 || dp[j + 1][i - 1]));
                if (dp[j][i] && len < i - j + 1) {
                    len = i - j + 1;
                    left = j;
                    right = i;
                }
            }
            dp[i][i] = 1;
        }
        return s.substr(left, right - left + 1);
    }
};
0%
undefined