原题地址为: https://leetcode.com/problems/substring-with-concatenation-of-all-words/
给定字符串s,和有一个单词列表words,每个词长度相等。在s中寻找,包含全部词,且每个词只出现一次,没有任何多余其他字符的子串。
s = “barfoothefoobarman”,
words = [“foo”,”bar”]
输出: [0,9]
0,9分别对应了”barfoor”和”foobar”
s = “wordgoodgoodgoodbestword”,
words = [“word”,”good”,”best”,”word”]
我的解题思路是这样的,首先这样的子串,一定也是words里面单词练在一起的某个组合。那么我们可以先调用438题目的函数findAnagrams。这样就大大减少了选项。
然后,我们从返回的list去检查,每一个子串,是否包含了words里面的单词,所以代码也不复杂。
不包含findAnagrams实现的话,包含两个函数,一个是checkwords,看看一个子串是否包含words里面的单词。另外一个函数是结果函数 findSubstring。
这个做起来简单,但是性能一般,执行需要94ms。问题应该出在checkwords的实现,不过我暂时懒得优化了,毕竟这次主要目的是练习滑动窗口的技巧。
本题代码地址为: https://github.com/tinyfool/leetcode/tree/master/src/p0030
本文假设你对滑动窗口概念有所了解,如果你对滑动窗口的概念不够了解,请参看我介绍 滑动窗口的文章,里面有详细的解释 。