LC214. Shortest Palindrome
Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.
For example:
Given "aacecaaa", return "aaacecaaa".
Given "abcd", return "dcbabcd".
返回字符串的最短回文，这题我的想法是找到字符串里面的回文然后再扩展开来，不过怎么找呢？如果DP做法，每一个substring都分析一遍的话，O(n!) ??? 显然不对啊tag里都没写DP呢。再一看String题，kmp, trie？
看了看题解，KMP解法，构造t = s + “❤” + s.reverse(). 题目要求在字符串前面加字符构造回文，因此对于t的next数组，最后一位是与s前缀重复的位置，也就是s内回文子序列的结束位置。保留回文子序列，加入substring的倒叙就得到了最短的回文。
public class Solution {
public String shortestPalindrome(String s) {
// str = s + "#" + s.reverse
// find the KMP.next array of str, (s.length - str.next[end] + 1) is the number of char add to head
if(s == null || s.length() == 0) return s;
String str = s + "#" + new StringBuilder(s).reverse().toString();
char[] arr = str.toCharArray();
int[] next = new int[str.length()];
Arrays.fill(next, -1);
int i = 0, j = 1;
for(;j < next.length; j++){
i = next[j - 1];
while(arr[i + 1] != arr[j] && i >= 0) i = next[i];
if(arr[i + 1] == arr[j]) next[j] = i + 1;
else next[j] = -1;
} // for
return new StringBuilder(s.substring(next[next.length-1]+1)).reverse().toString()+s;
}
}
最近怎么这么多KMP题🍥
好想吃火锅呀🍲