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.

题目大意

给定一个字符串 S，通过将字符串 S 中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。

解题思路

• 输出一个字符串中字母变大写，小写的所有组合。
• 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)
}

---