-
Notifications
You must be signed in to change notification settings - Fork 1
/
vowel.go
88 lines (84 loc) · 1.88 KB
/
vowel.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
package vowel
func countVowelString(n int) int {
return useBruteForce(n)
}
// useBruteForce time complexity O(N^2), space complexity O(N)
func useBruteForce(n int) int {
// n = 1 => 5
// n = 2 => 15
// a, e, i , o ,u, e, i, o ,u, i, o, u, o, u, u
// n = 3
// a -> a, e, i, o, u
// e -> e, i ,o, u
// i -> i, o, u
// o -> o, u
// u -> u
// aa, ae, ai, ao, au, ee, ei, eo, eu, ii, io, iu, oo, ou, uu, ee, ei, eo,eu
set := make(map[int]int, n)
set[1] = 5
set[2] = 15
nd := []byte{'a', 'e', 'i', 'o', 'u', 'e', 'i', 'o', 'u', 'i', 'o', 'u', 'o', 'u', 'u'}
factor := map[byte]int{'a': 5, 'e': 4, 'i': 3, 'o': 2, 'u': 1}
for i := 3; i <= n; i++ {
var local int
for i := range nd {
local += factor[nd[i]]
}
sb := make([]byte, 0, local)
for i := range nd {
switch nd[i] {
case 'a':
sb = append(sb, 'a', 'e', 'i', 'o', 'u')
case 'e':
sb = append(sb, 'e', 'i', 'o', 'u')
case 'i':
sb = append(sb, 'i', 'o', 'u')
case 'o':
sb = append(sb, 'o', 'u')
case 'u':
sb = append(sb, 'u')
}
}
nd = sb
set[i] = local
}
return set[n]
}
// useDP time complexity O(N*K), space complexity O(N*K)
func useDP(n int) int {
// dp[n][k] means the number of strings constructed by at most k different characters.
// for example
// k = 1 use `u`
// k = 2 use `o. u`
// etc.
dp := make([][]int, n+1)
for i := range dp {
dp[i] = make([]int, k+1)
}
for i := 1; i <= n; i++ {
for k := 1; k <= 5; k++ {
dp[i][k] = dp[i][k-1]
if i > 1 {
dp[i][k] += dp[i-1][k]
} else {
dp[i][k] += 1
}
}
}
return dp[n][5]
}
// useDPWithConstantSpace time complexity O(N*K), space complexity O(1)
func useDPWithConstantSpace(n int) int {
// n = 1 {1,1,1,1,1}
// n = 2 {5,4,3,2,1}
// n = 3 {15,10,6,3,1}
perm := [5]int{1, 1, 1, 1, 1}
for i := 1; i <= n; i++ {
sum := 0
for j := 4; j >= 0; j-- {
perm[j] += sum
sum = perm[j]
}
}
return perm[0]
}