xiaoyu

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"

解法一: 枚举 + 贪心

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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 函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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);
}

 评论