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