30。连接所有单词的子字符串全单词主题被赋予一个字符串s和一些相同长度的单词words。找到s中恰好由words中的所有单词拼接而成的子串的开头。注意子串必须完全匹配words中的单词，中间不能有其他字符，但是不需要考虑words中单词的拼接顺序。示例1：输入：s="barfoothefoobarman",words=["foo","bar"]输出：[0,9]解释：从索引0和9开始的子字符串分别是“barfoo”和“foobar”。输出顺序无关紧要，[9,0]也是一个有效答案。例子2：输入：s="wordgoodgoodgoodbestword",words=["word","good","best","word"]输出：[]解题思路：滑动窗口先试试用最简单的idea看可以它解决了问题。题目说我们需要找到子串和words中单词的精确匹配。那么最简单的思路就是判断子串是否匹配，如果匹配则将索引放入链表中，最后返回。具体方法如上图所示，循环遍历索引判断子串是否匹配。这里的主要问题是如何判断子串是否匹配？标题中有提示【注意子串必须完全匹配words中的单词，中间不能有其他字符，但不需要考虑words中单词的拼接顺序。]，也就是说标题不要求子串顺序完整，只需要数量相等，中间连接部分不会有其他字符。这算作匹配。这里，我们可以借助哈希表来解决。哈希表存储单词的信息，键存储单词，值存储单词出现的次数。另一个哈希表也存储单词作为键，存储单词的数量作为值。在遍历字符串的同时维护这个哈希表，然后和之前哈希表中的值进行比较。这里会出现如下情况：当遍历中存储的值大于存储单词的哈希表中的值时，显然不成立。当下一个子串小于时进行判断，再进行判断。当子串完全匹配时，这就是要查找的子串，它的索引存入列表，最后返回。但是这里不需要移动1个字符来匹配。题目中提到【somewordswiththesamelength】，也就是说words中的单词都是一样长的。这样，每次移动可以移动的偏移量就是单词的长度。然后对单词使用滑动窗口，步长为单词word_len的长度。然后在0~word_len的范围内，将其中的每一个都作为滑动窗口的起点，滑动可以覆盖所有的字符串组合。下图是示例1和使用滑动窗口的粗略图解：示例1输入：s="barfoothefoobarman",words=["foo","bar"]输出：[0,9]具体实现代码如下如下。代码实现类解决方案：deffindSubstring(self,s:str,words:List[str])->List[int]:fromcollectionsimportCounter#处理特殊情况ifnotsornotwords:return[]#HashtableCountword_cnt=Counter(words)#wordlengthword_len=len(words[0])#返回结果列表ans=[]#遍历，窗口滑动foriinrange(word_len):left=iright=icnt=0#哈希表记录了窗口中单词出现的次数window=Counter()#限制边界#这里表示窗口的内容不足以构成拼接所有单词的子串,循环结束whileleft+len(words)*word_len<=len(s):#单词在窗口中出现的次数，与word_cnt相比whilecnt
