-
Notifications
You must be signed in to change notification settings - Fork 2
/
findSubstring.go
55 lines (51 loc) · 1.76 KB
/
findSubstring.go
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
46
47
48
49
50
51
52
53
54
55
package substringwithconcatenationofallwords
func findSubstring(s string, words []string) []int {
if len(s) == 0 || len(words) == 0 || len(s) < len(words)*len(words[0]) {
return []int{}
}
lenWs, lenW, end := len(words), len(words[0]), len(s)-len(words)*len(words[0])
remain := make(map[string]int, lenWs)
result := make([]int, 0, end/lenW)
for offset := 0; offset < lenW; offset++ { // offset = [0, length of word)
// reset remain mapping
for _, word := range words {
remain[word] = 0
}
for _, word := range words {
remain[word]++
}
// start: the starting indices
// count: the count of matching words
for start, count := offset, 0; start <= end; {
word := s[start+count*lenW : start+(count+1)*lenW] // the word
if n, ok := remain[word]; ok { // if match word
if n == 0 { // if match word more than once
remain[s[start:start+lenW]]++ // restore the first word count
start += lenW // move start to next word
count-- // restore one count of matching words
} else { // match word exactly once
remain[word]--
if count++; count == lenWs {
result = append(result, start) // append the one of indices
remain[s[start:start+lenW]]++ // restore the first word count
start += lenW // move start to next word
count-- // restore one count of matching words
}
}
} else { // has any intervening characters
if count != 0 {
// reset remain mapping
for _, word := range words {
remain[word] = 0
}
for _, word := range words {
remain[word]++
}
}
start += lenW * (count + 1) // reset start
count = 0 // reset count
}
}
}
return result
}