Python O(n) Time, O(1) Space

  • 6

    Hash the number of times each character appears in p. Iterate over s with a sliding window and maintain a similar hash. If these two hashes are ever the same, add that to the result.

    Each of the hashes have a finite (a-z, A-Z) number of possible characters, so the space used is O(1)

    We iterate over s linearly, comparing constant length hashes at each iteration so each iteration is also O(1), so the runtime is O(n)

    class Solution(object):
        def findAnagrams(self, s, p):
            :type s: str
            :type p: str
            :rtype: List[int]
            res = []
            n, m = len(s), len(p)
            if n < m: return res
            phash, shash = [0]*123, [0]*123
            for x in p:
                phash[ord(x)] += 1
            for x in s[:m-1]:
                shash[ord(x)] += 1
            for i in range(m-1, n):
                shash[ord(s[i])] += 1
                if i-m >= 0:
                    shash[ord(s[i-m])] -= 1
                if shash == phash:
                    res.append(i - m + 1)
            return res

  • 0

    is the '[0]*123' come from ASCII code?

  • 1

    yes indeed! The two lists sHash and pHash contain 123 elements, one for each ASCII value from the strings s and p. This is a really cool way to count the frequency of each letter in the string. I also loved the efficiency of adding a single letter to sHash, and then checking whether the sHash ==pHash.

  • -1

    @ZhengwuFang Your English is really bad man

  • 0

    @ngaikw You are really polite and cultivated.

Log in to reply

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