Simple Python solution with detailed explanation

  • 0

    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
            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
                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.