[LeetCode] Longest Palindromic Substring 最长回文串

0
0
0
1. 云栖社区>
2. 博客>
3. 正文

## [LeetCode] 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, and there exists one unique longest palindromic substring.

```// Time complexity O(n*n)
class Solution {
public:
string longestPalindrome(string s) {
int startIdx = 0, left = 0, right = 0, len = 0;
for (int i = 0; i < s.size() - 1; ++i) {
if (s[i] == s[i + 1]) {
left = i;
right = i + 1;
searchPalindrome(s, left, right, startIdx, len);
}
left = right = i;
searchPalindrome(s, left, right, startIdx, len);
}
if (len == 0) len = s.size();
return s.substr(startIdx, len);
}
void searchPalindrome(string s, int left, int right, int &startIdx, int &len) {
int step = 1;
while ((left - step) >= 0 && (right + step) < s.size()) {
if (s[left - step] != s[right + step]) break;
++step;
}
int wide = right - left + 2 * step - 1;
if (len < wide) {
len = wide;
startIdx = left - step + 1;
}
}
};```

dp[i, j] = 1                                               if i == j

= s[i] == s[j]                                if j = i + 1

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

```// DP
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);
}
};```

```class Solution {
public:
string longestPalindrome(string s) {
string t ="\$#";
for (int i = 0; i < s.size(); ++i) {
t += s[i];
t += '#';
}
int p[t.size()] = {0}, id = 0, mx = 0, resId = 0, resMx = 0;
for (int i = 0; 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 (resMx < p[i]) {
resMx = p[i];
resId = i;
}
}
return s.substr((resId - resMx) / 2, resMx - 1);
}
};```

+ 关注