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".
https://leetcode.com/problems/shortest-palindrome/
Solution: O(N^2)
find the longest palindrome string start from index 0
public String shortestPalindrome(String s) {
if (s == null || s.length() <= 1)
return s;
String result = null;
int len = s.length();
int mid = len / 2;
for (int i = mid; i >= 1; i--) {
if (s.charAt(i) == s.charAt(i - 1)) {
if ((result = scanFromCenter(s, i - 1, i)) != null)
return result;
} else {
if ((result = scanFromCenter(s, i - 1, i - 1)) != null)
return result;
}
}
return result;
}
private String scanFromCenter(String s, int l, int r) {
int i = 1;
//scan from center to both sides
for (; l - i >= 0; i++) {
if (s.charAt(l - i) != s.charAt(r + i))
break;
}
//if not end at the beginning of s, return null
if (l - i >= 0)
return null;
StringBuilder sb = new StringBuilder(s.substring(r + i));
sb.reverse();
return sb.append(s).toString();
}
Solution: O(N) but not explanation
https://leetcode.com/discuss/51223/my-7-lines-recursive-java-solution
public class Solution {
public String shortestPalindrome(String s) {
int j = 0;
for (int i = s.length() - 1; i >= 0; i--) {
if (s.charAt(i) == s.charAt(j)) { j += 1; }
}
if (j == s.length()) { return s; }
String suffix = s.substring(j);
return new StringBuilder(suffix).reverse().toString() + shortestPalindrome(s.substring(0, j)) + suffix;
}
}
Solution: KMP, O(N)
https://leetcode.com/discuss/52564/a-kmp-based-java-solution-with-explanation
public class Solution {
public String shortestPalindrome(String s) {
if(s.length()<=1) return s;
String new_s = s+"#"+new StringBuilder(s).reverse().toString();
int[] position = new int[new_s.length()];
for(int i=1;i<position.length;i++)
{
int pre_pos = position[i-1];
while(pre_pos>0 && new_s.charAt(pre_pos)!=new_s.charAt(i))
pre_pos = position[pre_pos-1];
position[i] = pre_pos+((new_s.charAt(pre_pos)==new_s.charAt(i))?1:0);
}
return new StringBuilder(s.substring(position[position.length-1])).reverse().toString()+s;
}
}