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


  • 10
    M

    @ngaikw You are really polite and cultivated.


  • 2
    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!


  • 0
    E

    @dhgtfui He might not need 123 elements, he only need a-zA-Z 52 elements in total


  • 0
    R

    '''shash[ord(s[i-m])] -= 1'''
    can anyone please help explain this line? Thanks!


Log in to reply
 

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