Another O(n) time & O(n) space solution using hashes (Rabin-Karp algorithm)


  • 0
    J

    Surprisingly, I didn't find solution with hashes, so I decided to share it

    class Solution {
    public:
        string shortestPalindrome(string s) {
            int n = s.size();
            
            if (n < 2) {
                return s;
            }
            
            vector<unsigned int> hashes(n);
            vector<unsigned int> reverse_hashes(n);
            
            const unsigned int base = 31;
            unsigned int hash = 0;
            unsigned int power = 1;
            
            vector<unsigned int> powers(n);
            
            for (int i = 0; i < n; i++) {
                powers[i] = power;
                unsigned int v = s[i] - 'a' + 1;
                hash += v * powers[i];
                hashes[i] = hash;
                power *= base;
            }
    
            hash = 0;
            for (int i = n - 1; i >= 0; i--) {
                unsigned int v = s[i] - 'a' + 1;
                hash += v * powers[n - i - 1];
                reverse_hashes[i] = hash;
            }
    
            for (int k = 0; k <= n - 1; k++) {
                unsigned int h1 = hashes[n - k - 1];
                unsigned int h2;
                if (k > 0) {
                    h2 = reverse_hashes[0] - reverse_hashes[n - k];
                } else {
                    h2 = reverse_hashes[0];
                }
                if (h1 * powers[k] == h2) {
                    string prefix = s.substr(n - k);
                    reverse(prefix.begin(), prefix.end());
                    return prefix + s;
                }
            }
        }
    };
    

Log in to reply
 

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