LeetCode 784. 字母大小写全排列

约 4 分钟
文章信息 7 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节 华为
标签
字符串 位运算 回溯

题目描述

✅ 784. 字母大小写全排列

image-20260928224801125

题意分析

字符串只含英文字母和数字，每个字母可以独立选择大写或小写，数字保持不变。字符位置和顺序不变，要求列出所有大小写选择形成的字符串，结果顺序不限。

解法：按字符分支的 DFS 回溯

核心思路

[!blue]

定义 dfs(idx) 表示已经确定前 idx 个字符，接下来处理下标 idx；path 保存这段已确定的前缀，长度也恰好为 idx。当前字符是字母时，分别选择小写和大写；是数字时，只保留原字符。每次选择后递归处理下一位置。

递归返回后删除刚追加的字符，使 path 恢复到进入本层之前的状态。这样同一层的另一个选择会从相同前缀出发，不会混入上一分支留下的内容。

当 idx 到达字符串长度时，每个位置都已选择完毕，把 path 转成独立字符串加入结果。每种合法结果都对应一条完整选择路径，不会遗漏；不同路径至少在一个字母位置选择了不同大小写，得到的字符串也不同，因此不需要去重。

解题步骤

  • 初始化空路径和结果列表，从下标 0 开始递归。
  • 到达串尾时复制完整路径并返回。
  • 遇到字母，先追加它的小写形式、递归、撤销，再对大写形式做同样处理。
  • 遇到数字，只追加原字符、递归、撤销，不产生第二条分支。

Java 调用大小写转换方法；Go 在确认是英文字母后，通过设置或清除 ASCII 的 0x20 位转换大小写。无论输入原来是哪种大小写，都生成恰好两种选择；全为数字时只有一条路径，结果就是原字符串。

代码实现

class Solution {
    public List<String> letterCasePermutation(String s) {
        List<String> res = new ArrayList<>();

        backtrack(s.toCharArray(), 0, new StringBuilder(), res);

        return res;
    }

    private void backtrack(char[] chars, int idx, StringBuilder path, List<String> res) {
        if (idx == chars.length) {
            // 完整路径转成独立字符串，后续回溯不影响已收集结果
            res.add(path.toString());

            return;
        }

        char cur = chars[idx];

        if (cur >= 'a' && cur <= 'z' || cur >= 'A' && cur <= 'Z') {
            path.append((char) Character.toLowerCase(cur));
            backtrack(chars, idx + 1, path, res);
            // 撤销当前选择，恢复到进入本层之前的路径
            path.deleteCharAt(path.length() - 1);

            path.append((char) Character.toUpperCase(cur));
            backtrack(chars, idx + 1, path, res);
            // 撤销当前选择，恢复到进入本层之前的路径
            path.deleteCharAt(path.length() - 1);
        } else {
            path.append(cur);
            backtrack(chars, idx + 1, path, res);
            // 撤销当前选择，恢复到进入本层之前的路径
            path.deleteCharAt(path.length() - 1);
        }
    }
}

func letterCasePermutation(s string) []string {
    res := make([]string, 0)
    path := make([]byte, 0, len(s))

    var dfs func(int)
    dfs = func(idx int) {
        if idx == len(s) {
            // 完整路径转成独立字符串，后续回溯不影响已收集结果
            res = append(res, string(path))
            return
        }

        c := s[idx]
        if (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') {
            path = append(path, c|32)
            dfs(idx + 1)
            // 撤销当前选择，恢复到进入本层之前的路径
            path = path[:len(path)-1]

            path = append(path, c&^byte(32))
            dfs(idx + 1)
            // 撤销当前选择，恢复到进入本层之前的路径
            path = path[:len(path)-1]
        } else {
            path = append(path, c)
            dfs(idx + 1)
            // 撤销当前选择，恢复到进入本层之前的路径
            path = path[:len(path)-1]
        }
    }

    dfs(0)
    return res
}

复杂度分析

  • 时间复杂度：$O(n2^k)$，$n$ 为字符串长度，$k$ 为字母数量。共有 $2^k$ 个结果，每个结果复制 $n$ 个字符。
  • 空间复杂度：不计输出为 $O(n)$，来自递归栈和当前路径；结果本身占 $O(n2^k)$。

关键点总结

[!green]

  • 数字不应产生大小写分支。
  • 强制转换不依赖输入原来的大小写。
  • Go 的大小写位操作只用于本题英文字母，数字分支不修改。

易错点总结

[!yellow]

  • 对数字也清除大小写位，会生成控制字符。
  • 分支返回不撤销，会使后续结果长度异常。
  • 数字分支不追加，会丢失数字。

相似题目

题目 难度 关联与区别
78. 子集 中等 每个字母选择原大小写或翻转，对应逐位置二选一；数字只有保留一种选择。
17. 电话号码的字母组合 中等 同样每个位置从独立字符选项中取一个，完整结果是各组选项的笛卡尔积。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/92233202
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！