每天練LeetCode Quest Rolling Hash Q1. Shortest Palindrome

題目：

提供一個String s，需要在字串前加入文字，使其變為palindrome(回文)並回傳

思路：

由於做壞的情況是字串為s.substring(s.length()-2)+s

建立一個StringBuilder sb

使用forloop (int i = s.length — 1; i > 0 ;i — )

建立String newStr = sb.toString() + s;

int left = 0;

int right = newStr.length() — 1;

while(left<right)

當newStr.charAt(left) != newStr.charAt(right) break;

left++;

right — ;

當left==right || left>right return newString

sb每次新增s.charAt(i);

程式草稿：

public String shortestPalindrome(String s)

StringBuilder sb = new StringBuilder();

for(int i = s.length() — 1 ; i ≥ 0; i — )

String newStr = sb.toString()+s

int left = 0;

int right = newStr.length() — 1;

while(left<right)

if(newStr.charAt(left) ≠ newStr.charAt(right));

left++;

right — ;

if (left >= right) return newStr;

sb.append(s.charAt(i);

第一解Code：

class Solution {
    public String shortestPalindrome(String s) {
        StringBuilder sb = new StringBuilder();
        for(int i = s.length() - 1; i >= 0; i--){
            String newStr = sb.toString() + s;
            int left = 0;
            int right = newStr.length() - 1;
            while (left < right){
                if (newStr.charAt(left) != newStr.charAt(right)) break;
                left++;
                right--;
            }
            if (left >= right) return newStr;
            sb.append(s.charAt(i));
        }
        return "";
    }
}

結果：

Timeout，主要原因為runtime接近O(n^n)

查詢資料後，參考並嘗試使用kmp演算法解題

程式草稿：

public String shortestPalindrome(String s)

if(s == null || s.length() ≤ 1) return s;

String rev = new StringBuilder(s).reverse().toString();

String newStr = s + “#” + rev;

int[] next = new int[newStr.length()];

int i = 1, prev = 0;

while ( i < newStr.length())

if (newString.charAt(i) == newString.charAt(prev))

prev++;

next[i] = prev;

i++;

else

if( prev > 0)

prev = next[prev — 1];

else

next[i] = 0;

i++;

return new StringBuilder(s.substring(next[newStr.length() — 1]).reverse().toString() + s;

第二解Code：

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

結果：

執行成功，runtime表現良好

寫個小結論，KMP演算法會將O(M+N)的演算法，簡化為O(N)

雖然在CS中，處理大數據很厲害，但總給我一種脫褲子放屁的感覺