3. Longest Palindromic Substring
Given a string s, return the longest palindromic substring in s.
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
| class Solution {
public:
string longestPalindrome(string s) {
string p = "#";
for(auto ch : s) {
p += string(1,ch) + '#';
}
vector<int> dp(p.length());
int l = 0, r = -1;
for(int i = 1; i < p.length() - 1; i++) {
dp[i] = max(0, min(r - i, (l + r - i >= 0 ? dp[l + (r - i)] : -1)));
while(i - dp[i] >= 0 and p[i + dp[i]] == p[i - dp[i]])
dp[i]++;
if(r < i + dp[i]) {
l = i - dp[i];
r = i + dp[i];
}
}
int ma = -1, idx = -1;
for(int i = 1; i < dp.size(); i++) {
if(ma < dp[i]) {
idx = i;
ma = dp[i];
}
}
string res = "";
for(int i = idx - dp[idx] + 2; i < idx + dp[idx]; i+=2)
res += p[i];
return res;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
string longestPalindrome(string s) {
for(int i = 0; i < s.length(); i++) {
for(int start = 0; start <= i; start++) {
bool flag = true;
for(int distance = 0; distance < (s.length() - i) / 2; distance++) {
if(s[start + distance] != s[s.length() - 1 - i + start - distance]) {
flag = false;
break;
}
}
if(flag)
return s.substr(start, s.length() - i);
}
}
return "";
}
};
|
