My fingerprint based solution in c++ (4ms)


  • 2
    L

    The idea is to compute the fingerprints of the first k characters of the string, and fingerprints of the first k characters reversed. Then find the largest k where the fingerprint and reversed fingerprint of the first k characters are the same. Of course you verify s.substr(0, k) is a palindrome (it's likely to be) and continue finding if it's not.

    The key is that fingerprints can be computed in O(n) time.

    class Solution {
    public:
        static const int BASE = 19;
        string shortestPalindrome(string s) {
            int n = s.size();
            if (n == 0) {
                return "";
            }
            int fp[n];
            int fp_r[n];
            fp_r[0] = fp[0] = static_cast<int>(s[0]);
            int mul = BASE;
            for (int i = 1; i < n; ++i) {
                // it's ok to overflow.
                int tmp = static_cast<int>(s[i]);
                fp[i] = fp[i - 1] * BASE + tmp;
                fp_r[i] = fp_r[i - 1] + tmp * mul;
                mul *= BASE;
            }
            int i = n - 1;
            while (i) {
                if (fp[i] == fp_r[i] && verify(s, i)) {
                    break;
                }
                i--;
            }
            return string(s.rbegin(), s.rend()) + s.substr(i + 1, n - i - 1);
        }
        bool verify(const string& s, int idx) {
            for (int i = 0, j = idx; i < j; ++i, --j) {
                if (s[i] != s[j]) {
                    return false;
                }
            }
            return true;
        }
    };

  • 0
    T

    Very neat solution. Thanks for sharing.

    But the base value selection is kind of mysterious for me.

    I tried your code with 2 as base value, it got TLE for the very long all "a....a" case.

    Then I tried 3, it passed but used 8ms instead.

    I can imagine the base value, may have impact in some cases, as a small value like 2 may cause a lot false positive match and would cause more verify to be triggered.

    But, I really don't see why the base value would have impact on the all "a....a" case.

    Any thoughts on this, and why did you choose 19?


  • 0
    L

    I didn't quite remember the reason, but at least the BASE and 256 should be relatively prime, and that's why 3 performs much better than 2.


Log in to reply
 

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