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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
/**
解题思路:
这一题的关键点在于 "words 的长度相同"
这意味着采用移动窗口的方法对字符串检索的时候, 是以单个word的长度为单位跳跃的
因此, 如下的检索是以 `wordLen * wordNums` 为一整块, 从左到右以 wordLen 为 step 滑动
同时因为是单词, 所以起始点需要以 单个 wordLen 循环一遍, 这样能覆盖到全部字段
在函数中就体现在两个 for 循环上, 第一层循环单个 wordLen, 以对齐各个word, 第二层循环进行分段检测
*/
func findSubstring(s string, words []string) []int {
if len(words) == 0 || len(s) == 0 || len(s) < len(words[0])*len(words) {
return []int{}
}
wordLen := len(words[0])
wordNums := len(words)
sLen := len(s)
res := make([]int, 0)
l := wordLen * wordNums
var left, cursor int
right := l
reset := true
var m map[string]int8
for i := 0; i < wordLen; i++ {
left = i
cursor = left
right = left + l
fmt.Printf(">>>>>>>>> LOOP: left: %d, right: %d, string: %s \n", left, right, s[left:right])
if reset {
reset = false
m = map[string]int8{}
for _, w := range words {
m[w]++
}
}
for cursor < right && right <= sLen {
index := s[cursor : cursor+wordLen]
how, ok := m[index]
fmt.Printf("left: %d, cursor: %d, right: %d, string: %s \n", left, cursor, right, s[left:right])
fmt.Printf("index: %#+v, how: %#+v, ok: %#+v \n\n", index, how, ok)
if !ok {
if reset {
reset = false
m = map[string]int8{}
for _, w := range words {
m[w]++
}
}
left = cursor + wordLen
cursor = left
right = left + l
continue
}
if how <= 0 {
fmt.Printf("how < 0 , %s \n", s[left:left+wordLen])
m[s[left:left+wordLen]]++
left += wordLen
right += wordLen
continue
}
reset = true
m[index]--
cursor += wordLen
if cursor == right {
res = append(res, left)
m[s[left:left+wordLen]]++
left += wordLen
right += wordLen
}
}
}
return res
}
|