Q30 - Hard - 串联所有单词的子串

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

示例 1：

输入：
s = "barfoothefoobarman",
words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoor" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。
示例 2：

输入：
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
输出：[]

暴力 2000ms

class Solution:
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        if len(words) == 0 or len(s) == 0:
            return []
        n = len(words)
        len_word = len(words[0])
        len_words = len("".join(words))
        len_s = len(s)
        res = []
        
        for i in range(len_s - len_words + 1):
            window = s[i:i+len_words]
            l = []
            for word in words:
                l.append(word)
            for j in range(n):
                word = window[j*len_word:(j+1)*len_word]
                if word in l:
                    l.remove(word)
                else:
                    break
            if l == []:
                res.append(i)
        return res

64ms

class Solution:
    def findSubstring(self, s, words):
        if len(words) == 0:
            return []
        lens = len(s)
        lenw = len(words[0])
        lenws = lenw * len(words)
        if lens < lenws:
            return []
        counter = {}
        for i in range(len(words)):
            if words[i] in counter:
                counter[words[i]] += 1
            else:
                counter[words[i]] = 1
        res = []
        for i in range(min(lenw, lens-lenws + 1)):
            s_pos = word_pos = i
            d = {}
            while s_pos + lenws <= lens:
                # 截取单词
                word = s[word_pos:word_pos + lenw]
                # 移动到下一个单词
                word_pos += lenw
                if word not in counter:
                    s_pos = word_pos
                    d.clear()
                else:
                    if word not in d:
                        d[word] = 1
                    else:
                        d[word] += 1
                    while d[word] > counter[word]:
                        d[s[s_pos:s_pos + lenw]] -= 1
                        s_pos += lenw
                    if word_pos - s_pos == lenws:
                        res.append(s_pos)
        return res