Description
tags: String, Dynamic Programming
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"
My solution
(Expand Around Center)
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
int maxLen = 0;
string ret;
for (int i=0; i<n; i++) {
int l = i, r = i;
while (l > 0 && s[l-1] == s[i]) l--;
while (r < n-1 && s[r+1] == s[i]) r++;
while (l > 0 && r < n-1 && s[l-1] == s[r+1]) {
l--;
r++;
}
if ((r - l + 1) > maxLen) {
maxLen = (r - l + 1);
ret = s.substr(l, maxLen);
}
}
return ret;
}
};
Solution
Approach 1: Longest Common Substring
Approach 2: Brute Force
Time:
Space:
Approach 3: Dynamic Programming
Time:
Space:
Approach 4: Expand Around Center
Time:
Space:
Approach 5: Manacher's Algorithm
Time:
Space:
