题目分析

这个题目难度不大，还要小伙伴们仔细思考，不能因为难度是困难而放弃，有时候想一想也会豁然开朗。

滑动窗口

单词列表中的单词都已经告诉了，假设共有k个单词，每个单词长度为m，因此总长度mk也是已知的，所以我们可以维护一个滑动窗口，让窗口的长度等于单词的总长度，然后将其中的所有字符按照单词长度分成k份，看一看是否等于单词列表中的k个单词。如果相等则说明从该索引处可以完全匹配，否则窗口滑动到下一个索引。

假设字符串长度为n，算法需要滑动n次，每次滑动时要进行匹配，每次匹配最多要比较k次，每次比较的时间为m，只需要一个字典保存k个单词，因为k一般小于n，因此算法的**时间复杂度为$O(nmk)$，空间复杂度为$O(n)$**。

from collections import Counter


class Solution:
    def findSubstring(self, s, words):
        """
        :s: str
        :words: List[str]
        :rtype: List[int]
        """
        if not words:
            return []
        len_word, len_num = len(words[0]), len(words)
        length, res, dic = len_word * len_num, [], Counter(words)
        for i in range(len(s) - length + 1):
            if Counter([s[i + len_word * j: i + len_word * (j + 1)] for j in range(len_num)]) == dic:
                res.append(i)
        return res

优化滑动窗口

上面那种做法是可以的，但是没有充分利用长度相等这个条件。在上面的方法中，每次滑窗都需要统计单词出现的个数并且进行对比，对于如下情况s=”abcaababcaacabc”，word=[“abc”, “aab”]，当滑动窗口从索引0到索引5时，单词为”abcaab”是有效答案，如果按照上面的思路，下一步进行索引1到索引6，单词为”bcaaba”，不匹配，直到索引3到索引8才能再一次匹配，”aababc”是有效答案，在统计时，索引0到索引5有”aab”这个单词，索引3到索引8也有这个单词，我们没有利用到这个信息。

出现这个问题的缘故是我们每次只移动一个位置，如果我们能每次移动单词长度m的位置，那么下一个单词滑进窗口，滑窗中的第一个单词就会滑出窗口。那么中间的单词就可以进行充分利用。

因此需要两层循环，第一层循环单词的长度，作为滑窗的起始位置。还以刚刚的例子进行说明，word中的单词长度为3，因此第一层为0，1，2。当i=0时，将s分成[“abc”, “aab”, “abc”, “aac”, “abc”]，当i=1时，将s分成[“bca”, “aba”, “bca”. “aca”]，当i=2时，将s分成[“caa”, “bab”, “caa”, “cab”]。在第二层循环中，我们依次加入滑窗，当滑窗中单词个数为k时，进行比较。

算法第一层循环的次数为m，第二层循环的次数为n / k，每次要比较长度为k的字符是否相等，因此**时间复杂度为$O(nm)$，空间复杂度为$O(n)$**。

from collections import Counter


class Solution:
    def findSubstring(self, s, words):
        """
        :s: str
        :words: List[str]
        :rtype: List[int]
        """
        if not words:
            return []
        lens, word_lens, words_lens = len(s), len(words[0]), len(words)
        str_lens, res = word_lens * words_lens, []
        for i in range(word_lens):
            left = right = i
            cur_dic = Counter(words)
            while right + word_lens <= lens:
                if right - left < str_lens:
                    cur_dic[s[right: right + word_lens]] -= 1
                    right += word_lens
                    if right - left == str_lens and list(set(cur_dic.values())) == [0]:
                        res.append(left)
                else:
                    cur_dic[s[left: left + word_lens]] += 1
                    cur_dic[s[right: right + word_lens]] -= 1
                    left += word_lens
                    right += word_lens
                    if list(set(cur_dic.values())) == [0]:
                        res.append(left)
        return res

刷题总结

滑动窗口也是非常有趣的题目，小伙伴们要打破瓶颈，不要局限于滑窗的步长为1，要充分利用题目中隐藏的信息。