LeetCode 解题报告 (30)-- 双指针找拼接子字符串
原题如下:
>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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40class Solution(object):
def findSubstring(self, s, words):
"""
:type s: str
:type words: List[str]
:rtype: List[int]
"""
# 注意words中的词可能会重复
wordDict = {}
for word in words:
if word in wordDict:
wordDict[word] += 1
else:
wordDict[word] = 1
wordLen = len(words[0])
result = []
for i in range(len(s)-wordLen*wordNum+1):
tmp = s[i:i+wordLen]
tmpDict = {} # 存储words的临时list
if tmp in words:
head = i
while tmp in words and i < len(s)-wordLen+1:
if tmp in tmpDict:
tmpDict[tmp] += 1
else:
tmpDict[tmp] = 1
if tmpDict[tmp] > wordDict[tmp]:
tmpDict[tmp] -= 1
break
i += wordLen
tmp = s[i:i+wordLen]
if tmpDict == wordDict:
result.append(head)
else:
continue
return result
方法二
思路
这种方法参考了这里, 主要思想是利用了双指针围着当前符合 words(包括数量和种类)中的连续子字符串,同时计算围着的子字符串中 word 的数量。
巧妙的地方在于双指针当前包围的子字符串中如果含有某个 word 的数量大于 words 中这个 word 的数量时,移动左指针直到把这个 word 的数量减少。
这种方法的时间复杂度为 O (n), 提交时 AC 的时间约 100ms
实现代码
1 | class Solution(object): |