leetcode 214. 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".

 

 

构造最短的回文串。

 

 

1、自己写的暴力的方法：从中间向做判断，是否以pos为中点、word[0]为左边界构成回文串，如果是，那么返回结果即可。通过，但是很慢。

public class Solution {
public String shortestPalindrome(String s) {

int len = s.length();
if (len < 2){
return s;
        }
char[] word = s.toCharArray();
if (len % 2 != 0){
if (isParlindrome(word, len / 2, false)){
return s;
            }
        }
int pos = len / 2 - 1;
boolean isMid = false;
for (; pos >= 0; pos--){
if (isParlindrome(word, pos, true)){
                isMid = true;
break;
            }
if (isParlindrome(word, pos, false)){
break;
            }
        }
char[] newWord;
if (isMid == true){
            newWord = new char[len + len - pos * 2 - 2];
        } else {
            newWord = new char[len + len - pos * 2 - 1];
        }
for (int i = 0, j = 0; i < newWord.length - len; i++, j++){
            newWord[j] = word[len - 1 - j];
        }
for (int i = 0, j = newWord.length - len; i < len; i++, j++){
            newWord[j] = word[i];
        }
return String.valueOf(newWord);
    }

public boolean isParlindrome(char[] s, int mid, boolean isMid){

int left = mid - 1;
if (isMid == true){
            left = mid;
        }
int right = mid + 1;
while (left >= 0 && s[left] == s[right]){
            left--;
            right++;
        }
if (left == -1){
return true;
        } else {
return false;
        }
    }


}

 

 

2、利用KMP算法。参考discuss

//S is the pattern to be preprocessed
//output[i] is the failure index that output redirected to
public static int[] KMPpreprocess(String S){
int[] pi=new int[S.length()];
//init start of pi
    pi[0]=-1;
//get each index in pi, i is the index being processed
for (int i=1;i<pi.length;i++){
int j=pi[i-1];
while (j!=-1 && S.charAt(j+1)!=S.charAt(i)) {j=pi[j];}
if (j==-1){
if (S.charAt(0)==S.charAt(i)) pi[i]=0;
else pi[i]=-1;
        }
else if (S.charAt(j+1)==S.charAt(i)){
            pi[i]=j+1;
        }

    }

return pi;
}

public static String reverse(String s){
char[] outC=new char[s.length()];
for (int i=0;i<outC.length;i++){
        outC[i]=s.charAt(outC.length-1-i);
    }
return new String(outC);
}

public static String shortestPalindrome(String s) {
    String sPlus=s+"#"+reverse(s);
int[] PI=KMPpreprocess(sPlus);
int palinIndex=Math.min(PI[PI.length-1],s.length()-1);

    String nonPalin=s.substring(palinIndex+1);
    String Palin=s.substring(0,palinIndex+1);
return reverse(nonPalin)+Palin+nonPalin;
}