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 알고리즘 을 활용 한다.참고 토론

//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){
        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[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;
}

 
다음으로 전송:https://www.cnblogs.com/xiaoba1203/p/6645555.html