题目描述
给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。
返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。
示例 1：
输入：s = "a1b2"
输出：["a1b2", "a1B2", "A1b2", "A1B2"]
示例 2:
输入: s = "3z4"
输出: ["3z4","3Z4"]
提示:
1 <= s.length <= 12
s 由小写英文字母、大写英文字母和数字组成
题解
思路1:递归
从左往右依次遍历字符，过程中保持 ans 为已遍历过字符的字母大小全排列。
例如，当 S = "abc" 时，考虑字母 "a", "b", "c"，初始令 ans = [""]，依次更新 ans = ["a", "A"]， ans = ["ab", "Ab", "aB", "AB"]， ans = ["abc", "Abc", "aBc", "ABc", "abC", "AbC", "aBC", "ABC"]。
算法：
如果下一个字符 c 是字母，将当前已遍历过的字符串全排列复制两份，在第一份的每个字符串末尾添加 lowercase(c)，在第二份的每个字符串末尾添加 uppercase(c)。
如果下一个字符 c 是数字，将 c 直接添加到每个字符串的末尾。
static public func letterCasePermutation1(_ s: String) -> [String] {
let sArray = Array(s)
let n = sArray.count
if n < 1 {return [String]()}
var res = [String](repeating: "", count: 1)
for i in 0..<n {
if sArray[i].isLetter {
var tempres = [String]()
let size = res.count
for k in 0..<size {
var tempStr1 = res[k]
tempStr1.append(sArray[i].lowercased())
tempres.append(tempStr1)
var tempStr2 = res[k]
tempStr2.append(sArray[i].uppercased())
tempres.append(tempStr2)
}
res = tempres
}else{
let size = res.count
var tempres = [String]()
for k in 0..<size {
var tempStr1 = res[k]
tempStr1.append(String(sArray[i]))
tempres.append(tempStr1)
}
res = tempres
}
}
return res
}
优化
不使用额外的数组，在字符是字母遍历res数组过程中，将当前元素复制一份
static public func letterCasePermutation2(_ s: String) -> [String] {
let sArray = Array(s)
let n = sArray.count
if n < 1 {return [String]()}
var res = [String](repeating: "", count: 1)
for i in 0..<n {
if sArray[i].isLetter {
let size = res.count
for k in 0..<size {
// 复制一个元素
res.append(res[k])
res[k].append(sArray[i].lowercased())
res[size+k].append(sArray[i].uppercased())
}
}else{
let size = res.count
for k in 0..<size {
res[k].append(String(sArray[i]))
}
}
}
return res
}
思路2:二分掩码
假设字符串 S 有B个字母，那么全排列就有2^B 个字符串，且可以用位掩码 bits 唯一地表示。
例如，可以用 00 表示 a7b， 01 表示 a7B， 10 表示 A7b， 11 表示 A7B。注意数字不是掩码的一部分。
算法
根据位掩码，构造正确的全排列结果。如果下一个字符是字母，则根据位掩码添加小写或大写字母。 否则添加对应的数字
static public func letterCasePermutation3(_ s: String) -> [String] {
let sArray = Array(s)
let n = sArray.count
if n < 1 {return [String]()}
// 计算字母数量letterCount
// 最终结果数为1<<letterCount
var letterCount = 0
for i in 0..<n {
if sArray[i].isLetter {
letterCount += 1
}
}
var res = [String]()
for bits in 0..<(1<<letterCount) {
var tempStr:String = ""
var b = letterCount-1
for i in 0..<n {
if sArray[i].isLetter {
if ((bits >> b) & 1) == 1 {
tempStr.append(String(sArray[i].uppercased()))
}else{
tempStr.append(String(sArray[i].lowercased()))
}
b -= 1
}else{
tempStr.append(String(sArray[i]))
}
}
res.append(tempStr)
}
return res
}
