-
-
Notifications
You must be signed in to change notification settings - Fork 5.6k
/
784. Letter Case Permutation.go
85 lines (77 loc) · 1.75 KB
/
784. Letter Case Permutation.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
package leetcode
import (
"strings"
)
// 解法一,DFS 深搜
func letterCasePermutation(S string) []string {
if len(S) == 0 {
return []string{}
}
res, pos, c := []string{}, []int{}, []int{}
SS := strings.ToLower(S)
for i := 0; i < len(SS); i++ {
if isLowerLetter(SS[i]) {
pos = append(pos, i)
}
}
for i := 0; i <= len(pos); i++ {
findLetterCasePermutation(SS, pos, i, 0, c, &res)
}
return res
}
func isLowerLetter(v byte) bool {
if v >= 'a' && v <= 'z' {
return true
}
return false
}
func findLetterCasePermutation(s string, pos []int, target, index int, c []int, res *[]string) {
if len(c) == target {
b := []byte(s)
for _, v := range c {
b[pos[v]] -= 'a' - 'A'
}
*res = append(*res, string(b))
return
}
for i := index; i < len(pos)-(target-len(c))+1; i++ {
c = append(c, i)
findLetterCasePermutation(s, pos, target, i+1, c, res)
c = c[:len(c)-1]
}
}
// 解法二,先讲第一个字母变大写,然后依次把后面的字母变大写。最终的解数组中答案是翻倍增长的
// 第一步:
// [mqe] -> [mqe, Mqe]
// 第二步:
// [mqe, Mqe] -> [mqe Mqe mQe MQe]
// 第二步:
// [mqe Mqe mQe MQe] -> [mqe Mqe mQe MQe mqE MqE mQE MQE]
func letterCasePermutation1(S string) []string {
res := make([]string, 0, 1<<uint(len(S)))
S = strings.ToLower(S)
for k, v := range S {
if isLetter784(byte(v)) {
switch len(res) {
case 0:
res = append(res, S, toUpper(S, k))
default:
for _, s := range res {
res = append(res, toUpper(s, k))
}
}
}
}
if len(res) == 0 {
res = append(res, S)
}
return res
}
func isLetter784(c byte) bool {
return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')
}
func toUpper(s string, i int) string {
b := []byte(s)
b[i] -= 'a' - 'A'
return string(b)
}