C++ 6ms 8 lines KMP solution with comments


  • 0
    string shortestPalindrome(string s) {
            string mirror = string(s.rbegin(), s.rend()), str = s + '#' + mirror;   // build str for KMP process    
            int idx[str.length()]; idx[0] = -1;                                     // idx is KMP table, first element is always -1
            
            for (int i = 1; i < str.length(); i++) {                                // Configure KMP prefix table
                int preIdx = idx[i - 1];
                while (preIdx >= 0 && str[preIdx + 1] != str[i]) { preIdx = idx[preIdx]; }  // find longest prefix
                idx[i] = str[preIdx + 1] == str[i] ? preIdx + 1 : -1;               // set KMP table value
            }
    
            return mirror + s.substr(idx[str.length() - 1] + 1);                    
    }
    

  • 0

    This is like combining two steps together. Excellent


Log in to reply
 

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