Description
Given a string s, return the longest palindromic substring in s.
Example 1:
Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd"
Output: "bb"
Example 3:
Input: s = "a"
Output: "a"
Example 4:
Input: s = "ac"
Output: "a"
Solution
中心擴展法
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
class Solution {
public:
string longestPalindrome(string s) {
int max = 0, max_idx = 0;
for (int i = 0; i < s.size(); i++) {
int left = i - 1, right = i + 1;
int len = 1;
while (left >= 0 && right < s.size()) {
if (s[left] == s[right]) {
left--;
right++;
len += 2;
} else {
break;
}
}
if (len > max) {
max = len;
max_idx = left + 1;
}
}
for (int i = 1; i < s.size(); i++) {
int left = i - 1, right = i;
int len = 0;
while (left >= 0 && right < s.size()) {
if (s[left] == s[right]) {
left--;
right++;
len += 2;
} else {
break;
}
}
if (len > max) {
max = len;
max_idx = left + 1;
}
}
return s.substr(max_idx, max);
}
};
Runtime: 16 ms, faster than 89.02% of C++ online submissions for Longest Palindromic Substring.
Memory Usage: 7.1 MB, less than 89.16% of C++ online submissions for Longest Palindromic Substring.
