https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/
偷了两天懒，终于开始继续了。
一开始的思路比较简单。用一个指针指向 s 中，通过将 s 及其后面的字符串不断和 words 中的词比较（如果比较成功，就从 words 中删去该词），确定指针移动的方向和距离，并记录匹配的首个单词以及匹配次数的信息。
这种算法的复杂度太高（应该是 O(n*wordLen^2)），不过有时候需要回溯。
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
| func findSubstring(s string, words []string) []int {
ret:=[]int{}
if len(s)==0 || len(words)==0 {
return ret
}
wordLen:=len(words[0])
wordsUse:=make([]string,len(words))
copy(wordsUse,words)
foundHead:=-1
foundLen:=0
for i:=0;i+wordLen<=len(s); {
isFound:=false
for j,w:=range wordsUse {
if w==s[i:i+wordLen] {
wordsUse=append(wordsUse[:j],wordsUse[j+1:]...)
foundLen++
isFound=true
if foundHead<0 {
foundHead=i
}
break
}
}
if isFound {
if foundLen==len(words) {
ret=append(ret,foundHead)
i-=(foundLen-1)*wordLen
foundHead=-1
foundLen=0
}else{
i+=wordLen
}
}else{
i=i-foundLen*wordLen+1
wordsUse=make([]string,len(words))
copy(wordsUse,words)
foundHead=-1
foundLen=0
}
}
return ret
}
|
参考了 Solution 中的一个 O(n*len(words))的写法，他使用 Map 来简化每次查找字符串的时间。并且做到了只遍历len(words)次字符串。在每一次遍历的时候，窗口都只向前移动（每次移动wordLen个长度），而不用回溯。
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
| func findSubstring(s string, words []string) []int {
ret:=[]int{}
if len(s)==0 || len(words)==0 {
return ret
}
wordLen:=len(words[0])
wordMap:=make(map[string]int)
for _,w:=range words {
wordMap[w]+=1
}
for i:=0;i<wordLen;i++ {
tempMap:=make(map[string]int)
count:=0
left:=i
for j:=i;j+wordLen<=len(s);j+=wordLen {
tempS:=s[j:j+wordLen]
if v,ok:=wordMap[tempS];ok {
tempMap[tempS]+=1
if tempMap[tempS]<=v {
count++
}else{
for wordMap[tempS]<tempMap[tempS] {
tempS2:=s[left:left+wordLen]
tempMap[tempS2]-=1
if tempMap[tempS2]<wordMap[tempS2] {
count--
}
left+=wordLen
}
}
if count==len(words) {
ret=append(ret,left)
count--
tempMap[s[left:left+wordLen]]-=1
left+=wordLen
}
}else{
left=j+wordLen
count=0
tempMap=make(map[string]int)
}
}
}
return ret
}
|