030. Substring with Concatenation of All Words

题目链接:30. Substring with Concatenation of All Words

题目

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.

Example 1:

1
2
3
4
5
6
Input:
s = "barfoothefoobarman",
words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

分析

题目写的比较绕,简单来讲就是找出由 words 组成子串起始位置,words内可能会有重复元素。

找到的子串内不可以包含其他非words内的元素,也不可以多次使用words内元素。

双循环算法

  • 用字典来统计words中每个单词出现的次数。

  • 因为words中的单词都是相同大小的,所以可以直接从s中截取固定大小的子串判读是否在words中出现。

  • 每轮检测中,使用cur_dict判断减少次数,如果降为负数,则表示重复出现。

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
class Solution(object):
def findSubstring(self, s, words):
if len(words) == 0:
return []
wordsMap = {}
for word in words:
if word not in wordsMap:
wordsMap[word] = 1
else:
wordsMap[word] += 1
len_words = len(words[0])
num_words = len(words)
ans = []

for i in range(len(s) - len_words * num_words + 1):
j = 0
cur_dict = wordsMap.copy()
while j < num_words:
word = s[i + len_words * j:i + len_words * j + len_words]
if word not in wordsMap:
break
if word in cur_dict:
cur_dict[word] -= 1
if cur_dict[word] < 0:
break
j += 1
if j == num_words:
ans.append(i)
return ans

if __name__ == '__main__':
solu = Solution()
s, words = 'barfoothefoobarman', ['foo', 'bar']
print(solu.findSubstring(s, words))

最长子串算法

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
40
41
42
43
44
45
class Solution:
def findSubstring(self, s, words):
if not s or words==[]:
return []
lenstr=len(s)
lenword=len(words[0])
lensubstr=len(words)*lenword
times={}
for word in words:
if word in times:
times[word]+=1
else:
times[word]=1
ans=[]
for i in range(min(lenword,lenstr-lensubstr+1)):
# lenstr挨个来,所以只需lenword次即可
self.findAnswer(i,lenstr,lenword,lensubstr,s,times,ans)
return ans

def findAnswer(self,strstart,lenstr,lenword,lensubstr,s,times,ans):
wordstart=strstart
curr={}
while strstart+lensubstr<=lenstr:
word=s[wordstart:wordstart+lenword]
wordstart+=lenword
if word not in times:
strstart=wordstart
curr.clear()
else:
if word in curr:
curr[word]+=1
else:
curr[word]=1
# 如果大于已有的,尝试删除一些内容。
while curr[word]>times[word]:
curr[s[strstart:strstart+lenword]]-=1
strstart+=lenword
if wordstart-strstart==lensubstr:
ans.append(strstart)

if __name__ == "__main__":
test = Solution()
s, words = 'barfoothefoobarman', ['foo', 'bar']
print(test.findSubstring(s, words))

030. Substring with Concatenation of All Words

https://iii.run/archives/507686d21adf.html

作者

mmmwhy

发布于

2019-04-23

更新于

2021-05-30

许可协议