-
Notifications
You must be signed in to change notification settings - Fork 2
/
9. Problem Challenge 2 - String Anagrams.go
81 lines (60 loc) · 1.34 KB
/
9. Problem Challenge 2 - String Anagrams.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
/*
String Anagrams (hard)
Given a string and a pattern, find all anagrams of the pattern in the given string.
Anagram is actually a Permutation of a string. For example, “abc” has the following six anagrams:
abc
acb
bac
bca
cab
cba
Write a function to return a list of starting indices of the anagrams of the pattern in the given string.
Example 1:
Input: String="ppqp", Pattern="pq"
Output: [1, 2]
Explanation: The two anagrams of the pattern in the given string are "pq" and "qp".
Example 2:
Input: String="abbcabc", Pattern="abc"
Output: [2, 3, 4]
Explanation: The three anagrams of the pattern in the given string are "bca", "cab", and "abc".
*/
package main
import "fmt"
func mapsEqual(map1, map2 map[rune]int) bool {
if len(map1) != len(map2) {
return false
}
for k, v := range map1 {
if map2[k] != v {
return false
}
}
return true
}
func stringAnagram(a, b string) []int {
sol := make([]int, 0, len(a))
map1 := make(map[rune]int)
map2 := make(map[rune]int)
for _, c := range b {
map2[c]++
}
l := len(b)
for i, c := range a {
if i >= l {
t := rune(a[i-l])
map1[t]--
if map1[t] == 0 {
delete(map1, t)
}
}
map1[c]++
if mapsEqual(map1, map2) {
sol = append(sol, i-l+1)
}
}
return sol
}
func main() {
fmt.Println(stringAnagram("ppqp", "pq"))
fmt.Println(stringAnagram("abbcabc", "abc"))
}