Simple Python solution with detailed explanation


  • 0
    P

    """
    Approach: use dictionaries to check if two strings are anagrams.
    p_dict is fixed, while s_dict is changing based on the moving window.
    Construct s_dict based on substrings of s, each with length = len(p).
    More details on how to construct s_dict below

        This solution has O(n) in time complexity and O(m) in space complexity,
        where n is len(s) and m is len(p).
    

    """

        # Make sure to include from collections import Counter
    
        output = []
        p_dict = Counter(p)
        s_dict = Counter(s[:len(p)-1])
    
        for i in range(len(p)-1, len(s)):
            
            s_dict[s[i]] += 1           # Put/update new char (new character in the moving window) to s_dict.
            idx = i-len(p) + 1          # Index of the first char in the window.
            first = s[idx]              # First char in the window.
            
            if p_dict == s_dict:        # If two dictionaries are the same, we find an anagram
                output.append(idx)
                
            if s_dict[first] == 1:      # If s_dict[first] is 1, which means 'first' (first char in the window)
                del s_dict[first]       # will disapear in the next window
            else:
                s_dict[first] -= 1      # Otherwise, reduce its appearance by 1
                
        return output

Log in to reply
 

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