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


  • 7
    W

    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
    Z

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


  • 1
    J

    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.


  • -2
    N

    @ZhengwuFang Your English is really bad man


  • 8
    M

    @ngaikw You are really polite and cultivated.


  • 1
    H

    @ngaikw lol in computer science code judges


  • 0
    L

    @Wayne-x said in Python O(n) Time, O(1) Space:

    comparing constant length hashes at each iteration so each iteration is also O(1)

    Can you explain a little bit why you're comparing two hashes here? What I see is comparison of two lists phash and shash and the time complexity of comparing two lists should be O(n).


  • 0
    W

    @lizzy0127 Sure! So the runtime of iterating over a list depends on what the list contains. If we are iterating over a list that's given to us as the input, this would definitely be O(n). If we are iterating over a constant sized list, this is considered an O(1) operation. The two hashes we have here that we iterate over are constant sized.


  • 0
    D

    @jwang91 said in Python O(n) Time, O(1) Space:

    he two lists sHash and pHash contain 123 elements

    Why the two lists sHash and pHash contain 123 elements? How does this number (123) come from? Thanks!


Log in to reply
 

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