- Two Sum
Published:
5. 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.
Example 1:
Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.
Example 2:
Input: “cbbd”
Output: “bb”
manacher算法，时间复杂度O(n)，空间复杂度O(n)
class Solution {
public String longestPalindrome(String s) {
if(s == null || s.length() == 0) return "";
String str = manacherString(s);
int pR = -1;
int index = -1;
int[] pArr = new int[str.length()];
int[] res = new int[3];
for(int i = 0; i < str.length(); i++) {
pArr[i] = pR > i ? Math.min(pArr[2*index-i],pR-i) : 1;
while(i+pArr[i] < str.length() && i-pArr[i] > -1){
if(str.charAt(i+pArr[i]) == str.charAt(i-pArr[i])){
pArr[i]++;
}
else break;
}
if(i+pArr[i] > pR) {
pR = i+pArr[i];
index = i;
}
if(pArr[i] > res[2]) {
res[2] = pArr[i];
res[0] = (i-pArr[i]+1)/2;
res[1] = (i+pArr[i])/2;
}
}
return s.substring(res[0],res[1]);
}
public String manacherString(String s) {
int len = 2*s.length() + 1;
StringBuilder sb = new StringBuilder(len);
int index = 0;
for(int i = 0; i < len; i++) {
sb.append((i&1) == 0 ? '#' : s.charAt(index++));
}
return sb.toString();
}
}
求最长回文子串
将上述代码略微改改即可
进阶问题
添加字符使字符串成为回文序列
- 只能在末尾插入字符。通过manacher算法找到包含最后面字符的最长回文子串。
- 任意位置插入。通过manacher算法找到最长回文子串，然后通过前后子串比较插入。