0784. Letter Case Permutation

# 784. Letter Case Permutation#

## 题目 #

Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create.

Examples:

``````Input: S = "a1b2"
Output: ["a1b2", "a1B2", "A1b2", "A1B2"]

Input: S = "3z4"
Output: ["3z4", "3Z4"]

Input: S = "12345"
Output: ["12345"]
``````

Note:

• `S` will be a string with length between `1` and `12`.
• `S` will consist only of letters or digits.

## 解题思路 #

• 输出一个字符串中字母变大写，小写的所有组合。
• DFS 深搜或者 BFS 广搜都可以。

## 代码 #

``````
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 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)
}

``````

Sep 6, 2020