Python solution using dictionary - Minimum memory usage


  • 0
    A

    I used Python dictionaries to store the count of just relevant characters. While this is not the fastest solution, it uses the minimum required amount of memory.

    class Solution(object):
        def findAnagrams(self, s, p):
            """
            :type s: str
            :type p: str
            :rtype: List[int]
            """
            result = []
            dic_p, dic_s = {}, {}
            n_p, n_s = len(p), len(s)
            if n_s < n_p:
                return result
            for char in p:
                dic_p[char] = dic_p.get(char, 0) + 1
            list_chars = dic_p.keys() #list of characters in p that we care about
            for char in list_chars:
                dic_s[char] = 0 # Making an empty dictionary for keeping track of s
            for i in range(n_p): # Initiation of dic_s 
                if s[i] in list_chars:
                    dic_s[s[i]] += 1
            if dic_s == dic_p:
                result.append(0)
            for i in range(n_p, n_s):
                if s[i] in list_chars:# adding the new element
                    dic_s[s[i]] += 1
                if s[i - n_p] in list_chars:# removing the oldest element
                    dic_s[s[i - n_p]] -= 1
                if dic_s == dic_p: # Checking to see if we have anagram
                    result.append(i - n_p + 1)
            return(result)
    

Log in to reply
 

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