438. Find All Anagrams in a String

Given a string s and a non-empty string p, find all the start indices of p‘s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

Python

 
class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        result = []
        if not s:
            return []
        p_dict = dict()
        for _p in p:
            Solution.add_k_in_dict(_p, p_dict)
        s_dict = dict()
        index = 0
        for _s in s[index: index + len(p)]:
            Solution.add_k_in_dict(_s, s_dict)
        if s_dict == p_dict:
            result.append(index)
        index += 1
        while index+len(p) <= len(s):
            print index+len(p)
            Solution.del_k_from_dict(s[index-1], s_dict)
            Solution.add_k_in_dict(s[index+len(p)-1], s_dict)
            if s_dict == p_dict:
                result.append(index)
            index += 1
        return result

    @classmethod
    def add_k_in_dict(cls, k, k_dict):
        if k in k_dict:
            k_dict[k] += 1
        else:
            k_dict[k] = 1

    @classmethod
    def del_k_from_dict(cls, k, k_dict):
        if k in k_dict:
            k_dict[k] -= 1
        if k_dict[k] == 0:
            del k_dict[k]