30. 串联所有单词的子串

https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/

解法一：滑动窗口+直方图

数组中字符串等长（设长度为wl）很关键，利用这个条件，周期性的检测字符串即可。 外层循环：wl次 ，内层循环：n/wl次 ，复杂度O（n）

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        res = []
        n = len(s)
        cnt = len(words)
        if n == 0 or cnt == 0:
            return res
        dic = dict()
        for word in words:  #将数组中字符串存入字典，并统计频率
            if word in dic:
                dic[word] += 1
            else:
                dic[word] = 1

        wl = len(words[0])    #单词长度

        for i in range(wl):
            left, count = i, 0  #left记录窗口起点，count记录匹配次数
            tdic = dict()  #存储匹配中的字符串频率
            #窗口大小为wl，每次向前移动wl
            for j in range(i, n - wl + 1, wl):
                str = s[j : j+wl]  
                if str in dic:  #检测到words中字符串，写入tdic
                    if str in tdic:
                        tdic[str] += 1
                    else:
                        tdic[str] = 1
                    #若str数量合法，匹配数+1
                    if tdic[str] <= dic[str]:
                        count += 1
                    else:  #str数量超标，窗口向前滑动
                        while tdic[str] > dic[str]:
                            str1 = s[left : left+wl]
                            tdic[str1] -= 1
                            #注意：因为超标时没有增加匹配数，因此只有str数量合法才减少匹配数
                            if tdic[str1] < dic[str1]:
                                count -= 1
                            left += wl
                    if count == cnt:  #匹配次数符合，记录窗口起点到结果集
                        res.append(left)
                        # 窗口前移
                        tdic[s[left : left+wl]] -= 1
                        count -= 1
                        left += wl
                else:  #若不匹配，信息清空，窗口移动
                    tdic.clear()
                    count = 0
                    left = j + wl
        return res