LeetCode 214. Shortest Palindrome

Shortest Palindrome

How to do it with KMP?

public class Solution {
    public string ShortestPalindrome(string s) {
        int len = s.Length;
        int mid = len/2;
        if(len % 2 == 1){
            if(IsPal(s, mid,false)) return s;
        }
        for(int i = mid-1; i >= 0; i--){
            if(IsPal(s, i, true)) return ConstrPal(s, i, true);
            if(IsPal(s, i, false)) return ConstrPal(s, i, false);
        }
        return "";
    }
    
    private bool IsPal(string s, int i, bool isEven){
        int left, right;
        if(isEven) {
            left = i;
            right = i+1;
        } else {
            left = i-1;
            right = i+1;
        }
        while(left >= 0){
            if(s[left] != s[right]) return false;
            left -= 1;
            right += 1;
        }
        return true;
    }
    
    private string ConstrPal(string s, int i, bool isEven){
        StringBuilder sb = new StringBuilder();
        if(!isEven) sb.Append(s[i]);
        for(int j = i+1; j < s.Length; j++){
            sb.Append(s[j]);
            sb.Insert(0, s[j]);
        }
        return sb.ToString();
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *