3ms solution using hash


  • 0
    D
    class Solution {
    public:
        string shortestPalindrome(string s) {
            int p = 1000000009;
            int m = 1, a= 0 , b = 0, i = -1;
            for (int j = 0; j < s.size(); ++j) {
                a += m * s[j];
                m *=p;
                b = b*p + s[j];
                if (a == b) i = j;
            }
            string add = s.substr(i+1);
            reverse(add.begin(), add.end());
            return add + s;
        }
    };
    

Log in to reply
 

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