-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathN030SubstrWithConcat.go
More file actions
57 lines (52 loc) · 1.15 KB
/
N030SubstrWithConcat.go
File metadata and controls
57 lines (52 loc) · 1.15 KB
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
package main
type N030SubstrWithConcat struct {
}
func (this *N030SubstrWithConcat) findSubstring(s string, words []string) []int {
results := []int{}
wordsCount := len(words)
if wordsCount == 0 {
return results
}
wordLength := len(words[0])
totalLength := wordsCount * wordLength
sLength := len(s)
// Build a map<string, count>
mymap := make(map[string]int)
for _, word := range words {
_, ok := mymap[word]
if !ok {
mymap[word] = 1
} else {
mymap[word] += 1
}
}
sslice := []byte(s)
// For each substr, check if it exists in the map
for i := 0; i <= sLength-totalLength; i++ {
substr := string(sslice[i : i+wordLength])
_, ok := mymap[substr]
if ok {
check := make(map[string]int)
//copy(check, mymap)
for k := range mymap {
check[k] = mymap[k]
}
check[substr] -= 1
found := true
for j := 1; j < wordsCount; j++ {
nextSubstr := string(sslice[i+j*wordLength : i+j*wordLength+wordLength])
v2, ok2 := check[nextSubstr]
if !ok2 || v2 <= 0 {
found = false
break
} else {
check[nextSubstr] -= 1
}
}
if found {
results = append(results, i)
}
}
}
return results
}