A Python solution using large prime hashing but TLE


  • 0

    This solution is actually just for fun!

    from collections import Counter
    class Solution(object):
        def findAnagrams(self, s, p):
            """
            :type s: str
            :type p: str
            :rtype: List[int]
            """
            def hash(key):
                count = Counter(key)
                p1 = 2903
                p2 = 29947
                sHash = 0
                for c in string.ascii_lowercase:
                    sHash = sHash * p1 + count.get(c, 0)
                    p1 *= p2
                return sHash
    
            lenS = len(s)
            lenP = len(p)
            pKey = hash(p)
            ans = []
            countCache = Counter(p)
            i = 0
            while i < lenS - lenP + 1:
                j = i
                for j in range(i, i + lenP):
                    if s[j] not in countCache:
                        i = j
                        break
                if hash(s[i:i + lenP]) == pKey:
                    ans.append(i)
                i += 1
            return ans
    

  • 0

    This doesn't really make any sense. Why are you increasing p1? And what does this have to do with primes?


  • 0

    @StefanPochmann That's my way of calculating hash value. Primes are used to reduce the probability of collision. I just tried this method for fun.


  • 0

    But how does their primality play any role here? I don't get it.

    If you instead for example used p1 = len(p) + 1 and got rid of p2, that would lead to much smaller numbers, be faster, and completely prevent collisions. And it doesn't have anything to do with primality.


  • 0

    @StefanPochmann Yes, it is unncessary for this problem because I don't have a hashtable and no need to use MOD.


  • 0

    Btw, the last used p1 value, the one used to integrate the 'z' count, is 23533152042961000782017742135343373124751500529620718365033781944226810373144818245378113110086306257258279532858221. That's a whole lot of 'z' characters you're expecting :-)


  • 0

    Haha, I didn't expect that long. I knew this is impractical.


  • 0

    The size of that actually isn't the strangest thing about it. Stranger is that you treat the different characters differently. You're making sure that you can handle 23533152042961000782017742135343373124751500529620718365033781944226810373144818245378113110086306257258279532858220 'z' characters, but for 'b' you only make sure you can handle 86936140.


Log in to reply
 

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