给定一个字符串 s,你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
示例 1:
输入: "aacecaaa"
输出: "aaacecaaa"
示例 2:
输入: "abcd"
输出: "dcbabcd"
思路:这题O(N^2)的暴力方法没法过,因此我们可以考虑kmp算法,这样我们不用每次从头开始遍历,不懂的自行百度。
class Solution {
int ans,len,p,q;
public String shortestPalindrome(String s) {
int len=s.length();
StringBuilder rev=new StringBuilder();
for(int i=s.length()-1;i>=0;i--)
rev.append(s.charAt(i));
StringBuilder str=new StringBuilder();
for(int i=0;i<s.length();i++)
str.append(s.charAt(i));
str.append("#");
for(int i=s.length()-1;i>=0;i--)
str.append(s.charAt(i));
int n=str.length();
int[] f=new int[n];
for(int i=1;i<n;i++)
{
int t=f[i-1];
while(t>0 && str.charAt(t)!=str.charAt(i))
t=f[t-1];
if(str.charAt(t)==str.charAt(i))
t++;
f[i]=t;
}
return rev.substring(0,len-f[n-1])+s;
}
}