【2022-10-30每日一题】784. 字母大小写全排列[Medium]
2022-10-30
2分钟阅读时长
2022-10-30每日一题：784. 字母大小写全排列
难度：Medium
标签：位运算 、 字符串 、 回溯
给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。
返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。
示例 1：
输入：s = "a1b2" 输出：["a1b2", "a1B2", "A1b2", "A1B2"]
示例 2:
输入: s = "3z4" 输出: ["3z4","3Z4"]
提示:
1 <= s.length <= 12s由小写英文字母、大写英文字母和数字组成
方法一：回溯
个人写法
func letterCasePermutation(s string) (ans []string) {
n := len(s)
sb := []byte(s)
var dfs func (i int)
dfs = func(i int) {
if i == n {
ans = append(ans, string(sb))
return
}
dfs(i+1)
if sb[i] < '0' || sb[i] > '9' {
sb[i] ^= 32
dfs(i+1)
sb[i] ^= 32
}
}
dfs(0)
return ans
}
官方优化
func letterCasePermutation(s string) (ans []string) {
n, sb := len(s), []byte(s)
var dfs func (i int)
dfs = func(i int) {
// 跳过数字
for i < n && unicode.IsDigit(rune(sb[i])) {
i++
}
if i == n {
ans = append(ans, string(sb))
return
}
dfs(i+1)
sb[i] ^= 32 // 大小写转换
dfs(i+1)
sb[i] ^= 32 // 恢复
}
dfs(0)
return ans
}
复杂度分析
- 时间复杂度：O(n×2^n)。
- 空间复杂度：O(n×2^n)。
方法二：广度优先遍历
func letterCasePermutation(s string) (ans []string) {
q, n := []string{""}, len(s)
for len(q) > 0 {
cur := q[0]
pos := len(cur)
if pos == n {
ans = append(ans, cur)
q = q[1:]
} else {
if unicode.IsLetter(rune(s[pos])) { // 字母出来
q = append(q, cur + string(s[pos]^32))
}
q[0] += string(s[pos]) // 原地修改
}
}
return ans
}
复杂度分析
- 时间复杂度：O(n×2^n)。
- 空间复杂度：O(n×2^n)。
方法三：二进制位图
func letterCasePermutation(s string) (ans []string) {
// 统计字母个数
m := 0
for _, c := range s {
if unicode.IsLetter(c) {
m++
}
}
for mask := 0; mask < 1<<m; mask++ {
t, k := []rune(s), 0
for i, c := range t {
if unicode.IsLetter(c) {
if mask>>k&1 == 1 {
t[i] = unicode.ToUpper(c) // 第k位为1，转大写
} else {
t[i] = unicode.ToLower(c) // 第k位为0，转小写
}
k++
}
}
ans = append(ans, string(t))
}
return ans
}
复杂度分析
- 时间复杂度：O(n×2^n)。
- 空间复杂度：O(n×2^n)。