LeetCode--438. Find All Anagrams in a String（找到所有字符组合）Python

题目：

给定两个字符串s、p。找到s中和p包含相同字符的所有子串。

解题思路：

直接暴力搜索s，固定长度，对p和s固定长度的子串分别进行排序，看两者排序后是否相同。这样是一种方法，但会超时。

另外一种方法是使用哈希的方法。用两个个1*26的list分别存储p和s子串中各个字符出现的字数，对s进行滑动窗口，保持子串长度为p的长度。这样复杂度为O（n）。

代码（Python）：

class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        if len(s)<len(p):
            return []
        Dict = {}
        for i in range(26):
            Dict[chr(ord('a')+i)] = i
        
        p_char = [0]*26
        for i in p:
            p_char[Dict[i]] = p_char[Dict[i]]+1
        
        s_char = [0]*26
        n_p = len(p)
        n_s = len(s)
        
        output = []
        
        for i in range(n_p):
            s_char[Dict[s[i]]] = s_char[Dict[s[i]]]+1
            if s_char==p_char:
                output.append(0)
                
        for i in range(1,n_s-n_p+1):
            s_char[Dict[s[i-1]]] = s_char[Dict[s[i-1]]]-1
            s_char[Dict[s[i+n_p-1]]] = s_char[Dict[s[i+n_p-1]]]+1
            if s_char==p_char:
                output.append(i)
        return output