题目描述
给你一个字符串 s，找到 s 中最长的 回文 子串。
示例 1：
1
2
3
| 输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
|
算法思路
摆了一个51了，啥也没干，心里有点愧疚就来写道算法题，练练手感。这道题好像我做过，很有印象，最简单的一个做法就是中心拓展，顾名思义，找准一个回文中心，往两边枚举就行，但是一定要注意，回文子串的回文中心不一定是单字符，比如aba；还有可能是双字符，比如abba。因此写代码时可以分情况讨论。具体来说，我们可以遍历s[i]，然后从l = i-1, i-2, i-3,...,0; r = i+1, i+2,...,n-1看s[l]==s[r]，如果满足这个等式就是回文子串，不断增加长度即可；双对称中心同理，因此代码如下：
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| string longestPalindrome(string s) {
string res;
int max_index = -1;
int max_length = 0;
int flag = 0;
for (int i = 1; i < s.length() - 1; i++) {
int tmp_length = 1;
int l = i - 1;
int r = i + 1;
while(l >= 0 && r < s.length() && s[l] == s[r]) {
l--;
r++;
tmp_length += 2;
}
if (tmp_length > max_length) {
max_length = tmp_length;
max_index = i;
}
}
for (int i = 0, j = 1; i < s.length() - 1 && j < s.length(); i++, j++) {
if (s[i] != s[j]) {
continue;
}
int tmp_length = 2;
int l = i - 1;
int r = j + 1;
while(l >= 0 && r < s.length() && s[l] == s[r]){
l --;
r ++;
tmp_length += 2;
}
if (tmp_length > max_length) {
max_length = tmp_length;
max_index = i;
flag = 1;
}
}
if (max_length > 0) {
if (flag) {
int left = max_index - (max_length / 2 - 1);
res = s.substr(left, max_length);
}
else {
int left = max_index - (max_length - 1) / 2;
res = s.substr(left, max_length);
}
}
else {
res = s[0];
}
return res;
}
|
时间复杂度$O(N^2)$，这个没办法避免。
当然还有另一种思路就是动态规划，这里我和官方题解给的略微不同，官方题解用dp[i][j]表示以i开头j结尾的字符串是否是回文子串，然后再从头到尾遍历一遍dp得到最大值和最大回文串；我是使用dp[i][j]表示以i开头j结尾的回文子串的长度，如果他都不是回文子串了，那么必然是0。接下来我们看看状态转移方程：
还是很通俗易懂的，唯一一个要注意的地方就是这个公式的第一行，还需要dp[i+1][j-1]不等于0，不然的话原本子串都不是回文串了，还在这基础上+2就会导致错误累积了，比如babcab，中间的bc不是回文串，如果不判断的话，遍历到b~b，就会得到长度6。 并且我们在更新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
| string longestPalindrome(string s) {
int n = s.length();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
}
int max_length = 1;
int max_index = 0;
for (int i = n - 2; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
if (s[i] == s[j]) {
if (i + 1 == j) {
dp[i][j] = 2;
}
else {
if (dp[i+1][j-1] == 0) {
dp[i][j] = 0;
}
else {
dp[i][j] = dp[i+1][j-1] + 2;
}
}
if (dp[i][j] > max_length) {
max_index = i;
max_length = dp[i][j];
}
}
else {
dp[i][j] = 0;
}
}
}
return s.substr(max_index, max_length);
}
|
