Leetcode: 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".

本题最简单的思路是从后往前判断子串是否是回文串，然后把后面的弄到前面即可，不过这样仅仅能擦边通过测试

Brute Force: O(N^2), space O(1)

 1 public class Solution {
 2     public String shortestPalindrome(String s) {
 3         if (s==null || s.length()==0) return "";
 4         char[] arr = s.toCharArray();
 5         StringBuffer res = new StringBuffer();
 6         for (int i=arr.length-1; i>=0; i--) {
 7             if (isPalin(arr, 0, i)) {
 8                 res = new StringBuffer(s.substring(i+1));
 9                 res = res.reverse();
10                 break;
11             }
12         }
13         res.append(s);
14         return res.toString();
15     }
16     
17     public boolean isPalin(char[] arr, int l, int r) {
18         while (l < r) {
19             if (arr[l] != arr[r]) return false;
20             l++;
21             r--;
22         }
23         return true;
24     }
25 }

DP: O(N^2), space O(N^2)

 1 public class Solution {
 2     public String shortestPalindrome(String s) {
 3         //if (s==null || s.length()==0) return "";
 4         boolean[][] dict = new boolean[s.length()][s.length()];
 5         getdict(s, dict);
 6         int i = 0;
 7         for (i=s.length()-1; i>=0; i--) {
 8             if (dict[0][i]) break;
 9         }
10         StringBuffer res = new StringBuffer(s.substring(i+1));
11         res = res.reverse();
12         res.append(s);
13         return res.toString();
14     }
15     
16     public void getdict(String s, boolean[][] dict) {
17         for (int i=s.length()-1; i>=0; i--) {
18             for (int j=i; j<s.length(); j++) {
19                 if (s.charAt(i)==s.charAt(j) && (j-i<=2 || dict[i+1][j-1]))
20                     dict[i][j] = true;
21             }
22         }
23     }
24 }

KMP介绍：http://kb.cnblogs.com/page/176818/

实现：http://www.cnblogs.com/tonyluis/p/4474658.html

本题KMP：（未深究）参考：http://blog.csdn.net/pointbreak1/article/details/45931551

 1 public class Solution {
 2     public String shortestPalindrome(String s) {
 3         String result = "";
 4         if(s.length() == 0)
 5             return result;
 6         int[] prefix = new int[s.length() * 2];
 7         String mirror = s + new StringBuilder(s).reverse().toString();
 8         for(int i = 1; i < s.length() * 2; i++) {
 9             int j = prefix[i-1];
10             while(mirror.charAt(j) != mirror.charAt(i) && j > 0)
11                 j = prefix[j-1];
12             if(mirror.charAt(i) == mirror.charAt(j))
13                 prefix[i] = j + 1;
14             else
15                 prefix[i] = 0;
16         }
17         int count = s.length() - prefix[s.length() * 2 -1];
18         result = new StringBuilder(s.substring(s.length()-count, s.length())).reverse().toString() + s;
19         return result;
20     }
21 }