214. Shortest Palindrome

214. Shortest Palindrome

Question

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.

Example 1:

Input: "aacecaaa"
Output: "aaacecaaa"

Example 2:

Input: "abcd"
Output: "dcbabcd"

Thinking:

• Method：
  • 找到从0开始的最长对称，将剩余的字符在开头补全。

class Solution {
    public String shortestPalindrome(String s) {
        if(s == null || s.length() == 0) return s;
        int len = s.length();
        int max = 0;
        for(int i = 1; i <= len; i++){
            if(check(s.substring(0, i)))
                max = Math.max(max, i);
        }
        StringBuilder sb = new StringBuilder();
        for(int i = len - 1; i >= max; i--){
            sb.append(s.charAt(i));
        }
        sb.append(s);
        return sb.toString();
    }
    private boolean check(String s){
        char[] arr = s.toCharArray();
        int len = s.length();
        for(int i = 0; i < len / 2; i++)
            if(arr[i] != arr[len - 1 - i]) return false;
        return true;
    }
}

• Method 2: KMP
  • 找出s#s.reverse的最长相同前后缀。
  • KMP的next数组。

class Solution {
    public String shortestPalindrome(String s) {
        if(s == null || s.length() == 0) return s;
        String ss = s + "#" + new StringBuilder(s).reverse().toString();
        int[] next = new int[ss.length()];
        next[0] = -1;
        for(int i = 1, j = -1; i < ss.length(); i++){
            while(j > -1 && ss.charAt(i) != ss.charAt(j + 1))
                j = next[j];
            if(ss.charAt(i) == ss.charAt(j + 1)) j++;
            next[i] = j;
        }
        return new StringBuilder(s.substring(next[ss.length() - 1] + 1, s.length())).reverse().toString() + s;
    }
}

二刷

1. We can analyze one of the questions: aacecaaa
   • We first assume we have a result, a + aacecaaa, so we want to find the “a”.
   • We create a new String aacecaaa # aaacecaa, where the third part is the reverse of the string and the first part is the original string. So the created string is palindrone.
   • We want to find the longest common prefix and suffix. Where we find the a is the remain part of s, if not only a, we need to reverse the remain string.

     class Solution {
      public String shortestPalindrome(String s) {
       String ss = s + "#" + new StringBuilder(s).reverse().toString();
       int len = ss.length();
       int[] next = new int[len];
       next[0] = -1;
       for(int i = 1, j = -1; i < len; i++){
           while(j > -1 && ss.charAt(i) != ss.charAt(j + 1)){
               j = next[j];
           }
           if(ss.charAt(j + 1) == ss.charAt(i)) j++;
           next[i] = j;
       }
       return new StringBuilder(ss.substring(next[len - 1] + 1, s.length())).reverse().toString() + s;
      }
     }
     

Reference:

1. KMP