3ms c++ KMP based


  • 0
    H
    class Solution {
    public:
        string shortestPalindrome(string s) {
            // KMP, time: O(n), space: O(n)
            int n = s.length();
            if (n <= 1) return s;
            // lps table
            vector<int> lps(n, 0);
            int i = 1, len = 0;
            while (i < n) {
                if (s[i] == s[len]) lps[i++] = ++len;
                else {
                    if (len == 0) ++i;
                    else len = lps[len-1];
                }
            }
            // search reversed string based on lps
            i = 0;
            int j = n - 1;
            while (j >= 0) {
                if (s[j] == s[i]) { --j; ++i; }
                else {
                    if (i == 0) --j;
                    else i = lps[i-1];
                }
            }
            // extract pre info.
            string pre = "";
            for (int j = n - 1; j >= i; --j) 
                pre += s[j];
            return pre + s;
        }
    };
    

  • 0
    H

    same idea as in https://discuss.leetcode.com/topic/14526/c-8-ms-kmp-based-o-n-time-o-n-memory-solution, concise version

    class Solution {
    public:
        string shortestPalindrome(string s) {
            // KMP, time: O(n), space: O(n)
            if (s.size() <= 1) return s;
            string r = s;
            reverse(r.begin(), r.end());
            string t = s + "#" + r;
            // lps table for t
            vector<int> lps(t.size(), 0);
            int i = 1, len = 0;
            while (i < t.size()) {
                if (t[i] == t[len]) lps[i++] = ++len;
                else {
                    if (len == 0) ++i;
                    else len = lps[len-1];
                }
            }
            return r.substr(0, s.size() - lps.back()) + s;
        }
    };
    

Log in to reply
 

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