原题如下:
You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
For example, given:
s: “barfoothefoobarman”
words: [“foo”, “bar”]
You should return the indices: [0,9].
(order does not matter).
题目不难理解,实现也不难,关键是时间复杂度的控制。下面会讲述两种方法,第一种方法时间复杂度$O((n-k)*k)$,其中n为s的长度,k为所有的words拼接起来后的长度,这种方法提交时在TLE和AC间徘徊(即偶尔AC,偶尔TLE)。第二种方法时间复杂度为O(n),提交的时候能够AC。
方法一
思路
设wordLen为给出的words列表中每个词的长度,wordNum为给出的words列表的长度,n为给出的s的长度。
那么可以从头开始遍历s直到n-wordLen*wordNum+1,每次遍历用一个字典存储遍历中遇到的属于words的词语,并检查两者对应的词语的数量关系。遇到不属于words的词语或者字典中的某一词语的数量大于words中该词语的数量则跳出执行下一次的遍历
这种方法的时间复杂度$O((n-k)*k)$,n为s的长度。提交时偶尔TLE,偶尔AC,AC时显示的时间是876ms。
实现代码:
1 | class Solution(object): |
方法二
思路
这种方法参考了这里,主要思想是利用了双指针围着当前符合words(包括数量和种类)中的连续子字符串,同时计算围着的子字符串中word的数量。
巧妙的地方在于双指针当前包围的子字符串中如果含有某个word的数量大于words中这个word的数量时,移动左指针直到把这个word的数量减少。
这种方法的时间复杂度为O(n),提交时AC的时间约100ms
实现代码
1 | class Solution(object): |