5. Longest Palindromic Substring

题目

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

Example 1:

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

Example 2:

Input: “cbbd”
Output: “bb”

思路

动态规划法

假设字符串长度为n,那么我们可以用一个大小为dp[n][n]的二维数组来代表字符串状态。其中,dp[i][j]代表i~j区间的字符是否为回文串。

  • 当i=j时,只有一个字符,肯定是回文串;
  • i=j+1时,说明是相邻字符,只用判断s[i]是否等于s[j]
  • 当字符不相邻,也就是i-j>2时,判断s[i]是否等于s[j]以及dp[i+1][j-1]是否为回文串即可。

通过上面的分析可以写出递推公式如下:

1
2
3
4
5
dp[i, j] = 1   									//if i == j

dp[i, j] = s[i] == s[j] //if j = i + 1

dp[i, j] = s[i] == s[j] && dp[i + 1][j - 1] //if j > i + 1

例如,字符串aabba每一步dp的状态依次如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// a
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

// aa
1 1 0 0 0
0 1 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

// aab
1 1 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0

// aabb
1 1 0 0 0
0 1 0 0 0
0 0 1 1 0
0 0 0 1 0
0 0 0 0 0

// aabba
1 1 0 0 0
0 1 0 0 1
0 0 1 1 0
0 0 0 1 0
0 0 0 0 1

Manacher’s Algorithm 马拉车算法

http://www.cnblogs.com/grandyang/p/4475985.html
https://blog.csdn.net/dyx404514/article/details/42061017

最逆天的地方在于他把时间复杂度提高到了线性O(n)

代码

动态规划

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

Manacher’s Algorithm 马拉车算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//C++
string Manacher(string s) {
// Insert '#'
string t = "$#";
for (int i = 0; i < s.size(); ++i) {
t += s[i];
t += "#";
}
// Process t
vector<int> p(t.size(), 0);
int mx = 0, id = 0, resLen = 0, resCenter = 0;
for (int i = 1; i < t.size(); ++i) {
p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
while (t[i + p[i]] == t[i - p[i]]) ++p[i];
if (mx < i + p[i]) {
mx = i + p[i];
id = i;
}
if (resLen < p[i]) {
resLen = p[i];
resCenter = i;
}
}
return s.substr((resCenter - resLen) / 2, resLen - 1);
}
打赏