Is ok?My solution is ac!


  • 0
    N

    My idea comes from Sammax.But it's different.Am I right?

     class Solution
        {
        public:
            string shortestPalindrome(string s)
            {
                if (!s.size())
                    return "";
                auto pat = s + '#' + string (s.rbegin(), s.rend());
                int pLen = pat.size();
                vector<int> prefix(pLen, 0);
                for (int i = 1; i < pLen; ++i)
                {
                    int j = prefix[i - 1];
                    if (j > 0 && pat[i] != pat[j])
                        j = prefix[j - 1];
                    prefix[i] = (j += (pat[i] == pat[j]));
                }
                return string (s.rbegin(), s.rbegin()
                               + s.size() - prefix[pLen - 1]) + s;
            }
        };
    

Log in to reply
 

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