C++ 4 ms (O(n) time & O(n) memory) ,NOT using KMP. Just one pass.


  • 0
    B

    This code using a array palinIndex[i] to memory the longest palindrome string ended with i:
    palinIndex[i] indicates string ended with s[i] and started with s[palinIndex[i]] is a palindrome, that is,
    {palinIndex[i],...,i }construct a longest palindrome string.
    How to caculate palinIndex:

    1. just i, s[i] is a palindrome string,so palinIndex[i] = i;

    2. s[i-1]s[i] is palindrome ,so palinIndex[i] = i-1;

    1. s[i-2]s[i-2]s[i] is palindrome ,so palinIndex[i] = i - 2;
    1. {palinIndex[i-1],...i-1} is palindrome, so if s[palindrome[i-1] -1] == s[i], palinIndex[i] = palinIndex[i]-1;
    1. specially, for example "aaabcaaa". if palinIndex[i-1] == palinIndex[i-2], that is say {palinIndex[i-1],...,i-1} is same! so palinIndex[i] = palinIndex[i-1],if s[i] == s[palinIndex[i-1]];

    All test case is passed! IS THIS RIGHT? I don't konw ,may I miss some case!


    class Solution {
      public:
        string shortestPalindrome(string s) {
        string str = "";
        if(s.size() == 0)return str;
        int palinIndex[s.size()];
        int maxIndex = 0;
        palinIndex[0] = 0;
        for(int i = 1; i < s.size();i++){
            
            int index = i;
            if(i-1 >= 0 && s[i] == s[i-1]){
                index = i - 1;
            }
            if(i-2 >= 0 && s[i] == s[i-2]){
                index = i - 2;
            }
            if(palinIndex[i-1]-1 >= 0 && s[i] == s[palinIndex[i-1] - 1]){
                index = min(index,palinIndex[i-1] - 1);
            }
            if(i > 2 && palinIndex[i-1] == palinIndex[i-2]){
                if(s[i] == s[palinIndex[i-1]]){
                    index = min(index,palinIndex[i-1]);
                }
            }
            palinIndex[i] = index;
            if(index == 0){
                maxIndex = i;
            }
        }
        str = s.substr(maxIndex+1,s.size() - maxIndex);
        reverse(str.begin(),str.end());
        return str + s;
    }
    

    };


  • 1
    T

    Hello,The thoughts of your code is inspiring,but I think there might be some problem,for example when s[i]!=s[palinIndex[i-1]-1],and,palinIndex[i-1]!=palinIndex[i-2],your solutions just make palinIndex[i]=i-1||i-2,
    but it may be any number between palinIndex[i-1] to i,take this string an example:
    "dcbccccbccccbcd",it self is palindromic but throught this solution the result is "dcbccccbccccbcdcbccccbccccbcd"


  • 0
    B

    Thanks a lot :)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.