LeetCode longest-palindromic-substring

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1:

输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。

示例 2:

输入: "cbbd" 输出: "bb"

解答:

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
55
56
57
58
59
class Solution {
public:
string longestPalindrome1(string s) { // 法一,动态规划
int len = s.length();
if (len <= 1) return s;

int st = 0, maxLen = 1;

vector<vector<int>> dp(len, vector<int>(len)); // 二维数组

for (int i = 0; i < len; i++) {
dp[i][i] = 1; // 单个字符是回文的
if (i < len - 1 && s[i] == s[i+1]) { // 长度为 2 的回文串,两个字符相同
dp[i][i+1] = 1;
maxLen = 2;
st = i;
}
}

for (int k = 3; k <= len; k++) { // 从长度为 3 开始
for (int i = 0; i + k - 1< len; i++) { // i 为起始点
int ed = i + k - 1; // ed 为终点
if (s[i] == s[ed] && dp[i+1][ed-1] == 1) {
// 字串首末相同,且中间是回文串,那么它是回文串
dp[i][ed] = 1;
st = i;
maxLen = k;
}
}
}
return s.substr(st, maxLen);
}

string longestPalindrome2(string s) { // 法二,中心扩展
int len = s.length();
if (len <= 1) return s;

int st = 0, maxLen = 1;
for (int i = 0; i < len; i++) {
int len1 = expandAroundCenter(s, i, i); // 奇数回文
int len2 = expandAroundCenter(s, i, i + 1); // 偶数回文
int tmpLen = max(len1, len2);
if (tmpLen > maxLen) { // 更新结果
maxLen = tmpLen;
st = i - (maxLen - 1) / 2;
}
}
return s.substr(st, maxLen);
}

int expandAroundCenter(string s, int left, int right) {
int len = s.length(); // 中心扩展
while (left >= 0 && right < len && s[left] == s[right]) {
--left;
++right;
}
return right - left - 1; // 因为多扩展一次,所以长度 - 1
}
};

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×