-
Notifications
You must be signed in to change notification settings - Fork 2
/
8. Problem Challenge 1 - Permutation in a String.go
93 lines (70 loc) · 1.75 KB
/
8. Problem Challenge 1 - Permutation in a String.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
/*
Problem Challenge 1
Permutation in a String (hard)
Given a string and a pattern, find out if the string contains any permutation of the pattern.
Permutation is defined as the re-arranging of the characters of the string. For example, “abc” has the following six permutations:
abc
acb
bac
bca
cab
cba
If a string has ‘n’ distinct characters it will have n!n! permutations.
Example 1:
Input: String="oidbcaf", Pattern="abc"
Output: true
Explanation: The string contains "bca" which is a permutation of the given pattern.
Example 2:
Input: String="odicf", Pattern="dc"
Output: false
Explanation: No permutation of the pattern is present in the given string as a substring.
Example 3:
Input: String="bcdxabcdy", Pattern="bcdyabcdx"
Output: true
Explanation: Both the string and the pattern are a permutation of each other.
Example 4:
Input: String="aaacb", Pattern="abc"
Output: true
Explanation: The string contains "acb" which is a permutation of the given pattern.
*/
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 findPermutation(str string, pattern string) bool {
map1 := make(map[rune]int)
map2 := make(map[rune]int)
for _, c := range pattern {
map2[c]++
}
l := len(pattern)
for i, c := range str {
map1[c]++
if i >= l {
t := rune(str[i-l])
map1[t]--
if map1[t] == 0 {
delete(map1, t)
}
}
if mapsEqual(map1, map2) {
return true
}
}
return false
}
func main() {
fmt.Println(findPermutation("oidbcaf", "abc"))
fmt.Println(findPermutation("odicf", "dc"))
fmt.Println(findPermutation("bcdxabcdy", "bcdyabcdx"))
fmt.Println(findPermutation("aaacb", "abc"))
}