O(1) Space O(N) Time Python Solution Based on Polynomial Hashing

  • 1

    The key is to find a way to do high efficient string matching.
    Most solution are based on O(N) space KMP algo. Here I present another O(1) space solution.

    Define a string's polynomial function as

    Hash(s) = (c0*p^n + c1*p^(n-1) + ... cn) % m

    Therefore, it's O(1) to update the hash value when modify front or tail character.

    To demonstrate how does it work, let's play with an input like 'babcd'.

    Firstly, an O(N) Initialization

    forward = hash('babcd')
    reverse = hash('dcbab')

    Then we remove the tail from forward and head from reversed, update the hash value.

    Iteration 1:  hash('babcd') != hash('dcbab')
    Iteration 2:  hash('babc') != hash('cbab')
    Iteration 3:  has('bab') == hash('bab')

    Each iteration is O(1), so the overall complexity is O(N). And we only used two variables here:)

    class Solution:
        # @param {string} s
        # @return {string}
        def shortestPalindrome(self, s):       
            prime = 7
            modular = 1000
            length = len(s)
            forward = reverse = 0
            power = 1
            for i in range(length):
                forward = (forward * prime + ord(s[i])) % modular
                reverse = (reverse * prime + ord(s[length - i -1])) % modular
                power = power * prime % modular if i > 0 else power
            forward_power = 1
            for i in range(len(s)):
                if forward == reverse:
                    tmp = s[:len(s)-i]
                    if tmp == tmp[-1::-1]:
                        return s[len(s)-i:][-1::-1] + s
                # Remove tail from forward
                forward -= ord(s[len(s)-i-1]) * forward_power % modular
                forward = forward + modular if forward < 0 else forward
                forward_power *= prime
                # Remove head from reverse
                reverse -= ord(s[len(s)-i-1]) * power % modular
                reverse = reverse + modular if reverse < 0 else reverse
                reverse = reverse * prime % modular
            return s[::-1] + s[1:]

  • 1

    Interesting approach. Some comments/questions:

    • c2*p(n-1) is missing ^. And you start with c1*p^n and end with cn*p^0, that's an off-by-1 error.
    • What's the pass for? It doesn't do anything.
    • Why start the powers with 1, 1, 7, 49 instead of 1, 7, 49?
    • In each operation, you don't just change forward and reverse but potentially create and check a long substring, so it's not O(1) but O(n).

  • 0

    Thank you for pointing out the typo. The hash function is updated.

    The pass is a placeholder there, because I implemented the "update" part below then came back and finished the "return" part.

    For the reason "power" is begin with 1, 1, 7, 49. It's because the power is used for removing the head from "reverse" hash.

    A comparison is only required when found result or hash function collision. With a bigger prime and modular, we pass the test even without the verification. Try Prime=17, Modular=1000000.

Log in to reply

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