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"
我想到的和官方给出的中心扩展算法相同；
看起来效率还可以。
Runtime: 6 ms, faster than 92.17%
class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() <= 1) {
return s;
}
int start = 0;
int end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = getManacherLength(s, i, i);
int len2 = getManacherLength(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private int getManacherLength(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}
}
因为已经学习过DP算法了，试着写了个DP版本；
效率看起来比同样时间复杂度的中心扩展算法慢很多，应该和DP数组初始化有关系吧，空间占用
；
Runtime: 43 ms, faster than 39.00% of Java online submissions for Longest Palindromic Substring.
Memory Usage: 34.9 MB, less than 99.94% of Java online submissions for Longest Palindromic Substring.
class Solution {
public String longestPalindrome(String s) {
boolean[][] palindrome = new boolean[2][s.length()];
int maxLength = 0;
int start = 0;
for (int right = 0; right < s.length(); right++) {
for (int left = right; left >= 0; left--) {
if (s.charAt(right) == s.charAt(left)
&&(right - left < 3 || palindrome[(right-1)%2][left+1])){
palindrome[right%2][left] = true;
if (maxLength < right - left + 1){
maxLength = right - left + 1;
start = left;
}
}else{
palindrome[right%2][left] = false;
}
}
}
return s.substring(start,start + maxLength);
}
}
然后发现还有时间复杂度为的Manacher (马拉车) 算法，照着思路写了一下；
提交的测试时间和中心扩展算法差不多，应该是因为测试用例都是比较短的字符串。
Runtime: 6 ms, faster than 92.05% of Java online submissions for Longest Palindromic Substring.
Memory Usage: 35 MB, less than 99.91% of Java online submissions for Longest Palindromic Substring.
class Solution {
public String longestPalindrome(String s) {
int extendLength = s.length()*2 + 1;
int maxRight = 0;
int maxLength = 0;
int centerTemp = 0;
int startIndex = 0;
int[] lps = new int[extendLength];
for (int i = 0; i < extendLength; i++) {
int mirror = 2*centerTemp - i;
lps[i] = maxRight > i ? Math.min(maxRight - i, lps[mirror]) : 0;
while (i - lps[i] - 1 >= 0
&& i + lps[i] + 1 < extendLength
&& s.charAt((i - lps[i] - 1)/2) == s.charAt((i + lps[i])/2)){
lps[i]++;
}
if (maxRight < i + lps[i]){
maxRight = i + lps[i];
centerTemp = i;
}
if (maxLength < lps[i]){
maxLength = lps[i];
startIndex = (i - maxLength)/2;
}
}
return s.substring(startIndex,startIndex+maxLength);
}
}
参考链接：
Longest palindromic substring - Wikipedia
