-
Notifications
You must be signed in to change notification settings - Fork 0
/
solution.go
99 lines (87 loc) · 1.77 KB
/
solution.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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
package substring_with_concatenation_of_all_words
func FindSubstring(s string, words []string) []int {
if len(words) <= 0 {
return nil
}
wordLen := len(words[0])
windowWidth := wordLen * len(words)
if len(s) < windowWidth {
return nil
}
var want counter
for _, word := range words {
want.eat(word)
}
var window counter
window.eat(s[:windowWidth])
ws := initWordSearcher(words)
var result []int
for end := windowWidth; end <= len(s); end++ {
start := end - windowWidth
if window.match(&want) && ws.match(s[start:end]) {
result = append(result, start)
}
if end < len(s) {
window.increase(s[end])
}
window.decrease(s[start])
}
return result
}
type counter [26]int
func (c *counter) eat(s string) {
for i := 0; i < len(s); i++ {
c[s[i]-'a']++
}
}
func (c *counter) increase(b byte) {
c[b-'a']++
}
func (c *counter) decrease(b byte) {
c[b-'a']--
}
func (c *counter) match(other *counter) bool {
for i := 0; i < 26; i++ {
if c[i] != other[i] {
return false
}
}
return true
}
type wordSearcher struct {
counter map[string]int
wordLen int
}
func initWordSearcher(words []string) wordSearcher {
counter := make(map[string]int)
for _, word := range words {
if count, exists := counter[word]; exists {
counter[word] = count + 1
} else {
counter[word] = 1
}
}
return wordSearcher{
counter: counter,
wordLen: len(words[0]),
}
}
func (ws wordSearcher) match(s string) bool {
other := make(map[string]int)
for word, count := range ws.counter {
other[word] = count
}
for i := 0; i < len(s)/ws.wordLen; i++ {
word := s[i*ws.wordLen : (i+1)*ws.wordLen]
if count, exists := other[word]; exists {
if count <= 1 {
delete(other, word)
} else {
other[word] = count - 1
}
} else {
return false
}
}
return true
}