LeetCode 784. 字母大小写全排列

2026-03-14 HGNULB 约 8 分钟

文章信息 7 个分类 3 个标签

分类

题目描述

✅ 784. 字母大小写全排列

题意分析

输入是一个由字母和数字组成的字符串，最长 12。要为其中每个字母各自选定大写或小写，数字保持原样，输出所有能得到的字符串。

每个字母是独立的二选一，数字位没有任何选择余地。因此结果个数恰好是 $2^k$，$k$ 为字母个数；不同的选法必然产生不同的串，所以既不需要去重，输出顺序也不受限。

输入里的字母可能本来就是大写，例如 "C" 的答案是 ["c", "C"]。这一点决定了不能假设输入全小写，「变成另一种大小写」必须写成不依赖原始大小写的形式。

长度上限 12 意味着最多 4096 个结果，规模被刻意压得很小，说明题目本意就是让你老实枚举，重点在于不重不漏而不是降复杂度。

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

核心思路

输出规模本身就是 $2^k$，任何算法都必须把每个结果构造一遍，所以这题不存在「优化掉指数」的空间，唯一要保证的是每个结果恰好被生成一次。

一个容易想歪的做法是「先对每一位都分出两条支路，最后再过滤或去重」。数字位没有大小写之分，硬给它分支会产生成对的重复结果，去重的代价和调试成本都是白付的。

正确的切入点是逐位决策：从左往右处理，第 idx 位的选择集只有两种形态 —— 是字母就是 {小写, 大写} 两个选项，是数字就只有 {原样} 一个选项。这构成一棵深度为 n 的决策树，每条从根到叶的路径恰好对应一个结果，分支数不同的位自然就不会产生重复。

递归维持的不变量是：进入 dfs(idx) 时，path 恰好是 s[0 .. idx-1] 的某个完整变体、长度正好是 idx；dfs(idx) 返回后 path 必须恢复到原长。于是 idx == n 时 path 就是一个现成的合法答案，直接收下即可。

解题步骤

准备结果集 res 和共享的可变路径 path，从 idx = 0 开始递归。用一个共享的 path 而不是每层复制，是回溯相对于「层层传新串」的主要优势。

递归出口是 idx == n：把 path 转成字符串收进 res 并返回。出口条件必须是等于而不是大于，多走一层就会在取 s[idx] 时越界。

当前字符不是字母时只有一条支路：把它原样追加、递归、再弹出。注意即使不需要变换也必须追加，否则数字会从结果里凭空消失。

当前字符是字母时分两条支路：先追加小写版本递归，弹出后再追加大写版本递归，弹出。两支的弹出都不能省，它们各自负责把 path 还原到进入这一层时的长度。

求「另一种大小写」时要用与原值无关的写法。ASCII 里大小写只差第 5 个二进制位，所以小写是 c | 32、大写是 c &^ 32（Java 里用 toLowerCase 与 toUpperCase 同理）。若写成「原来是小写就减 32、否则加 32」，当输入本来就是大写时两条支路会算出同一个字符。

全程不需要对结果做去重，各条路径的选择序列互不相同，产出必然互不相同。

以 s = "a1B" 走一遍（n = 3，字母在下标 0 和 2）：

idx = 0 是字母 'a'，先走小写支：path = "a"，进入 idx = 1。

idx = 1 是数字 '1'，唯一支路：path = "a1"，进入 idx = 2。

idx = 2 是字母 'B'，先走小写支：path = "a1b"，进入 idx = 3 等于 n，收下 "a1b"。弹出后走大写支：path = "a1B"，进入 idx = 3，收下 "a1B"。再弹出，path 回到 "a1"。

逐层弹出回到 idx = 0，改走大写支：path = "A"，同样经过数字位得到 "A1"，再在 idx = 2 分出两支，依次收下 "A1b" 和 "A1B"。

最终 res = ["a1b", "a1B", "A1b", "A1B"]，共 $2^2 = 4$ 个，与两个字母各二选一的计数一致。这个用例同时覆盖了「输入含大写字母」和「数字位不分支」两处易错，值得作为默认自测样例。

代码实现

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(2^k \cdot n)$，其中 $k$ 是字母个数、$n$ 是串长。决策树有 $2^k$ 个叶子，每到叶子要把长度 $n$ 的路径构造成字符串；内部节点的总数与叶子数同阶，不改变量级。这个上界由输出规模决定，无法再降。

空间复杂度：$O(n)$，不计返回值本身。递归深度是 n，path 长度同样不超过 n，两者都与结果个数无关。

关键点总结

「每个位置独立做选择」是最基础的回溯形态。识别出各位的选择集是什么（这里是字母两选一、数字一选一），代码结构就被完全确定了。

让分支数随位置变化，比「统一分两支再去重」更省事也更不容易错。去重往往是在替某个建模缺陷擦屁股，值得先回头检查建模。

大小写切换要写成与原值无关的形式。c | 32 强制置位得小写、c &^ 32 强制清位得大写，这比「判断原来是大是小再加减 32」既短又不会在大写输入上翻车。

回溯的追加与弹出必须成对出现在每一条支路上，包括那条「不需要变换」的单支。漏掉单支的追加会让字符凭空消失，漏掉弹出会让兄弟分支拿到脏路径。

面试视角：这题还有一个不用递归的写法 —— 先取出所有字母的下标，再用 $0$ 到 $2^k - 1$ 的位掩码枚举每种组合。能同时给出回溯版和位掩码版，并说明后者省掉了递归栈，是很自然的加分点。

面试视角：注意题面叫「全排列」但实质是「每位二选一的组合枚举」，和 46 那种真正的排列问题不是一类。能主动澄清这个命名误导，说明你按结构而不是按标题在归类题目。

易错点总结

错误写法：把「另一种大小写」写成「原来是小写就减 32，否则加 32」，而第一条支路已经用 c | 32 产出了小写。用 s = "C" 试：第一支得 'c'，第二支因为 'C' 不是小写而走加 32，又得到 'c'，输出 ["c", "c"]，正确答案是 ["c", "C"]。

错误写法：对数字位也分出两条支路。用 s = "1" 试：'1' | 32 仍是 '1'，而 '1' &^ 32 得到码值 17 的控制字符，结果里会混进一个乱码串，正确答案只有 ["1"] 一个。

错误写法：非字母分支里只递归、忘了先把字符追加进 path。用 s = "a1" 试：数字被整个跳过，输出成 ["a", "A"]，正确答案是 ["a1", "A1"]。

错误写法：递归返回后忘记弹出。用 s = "ab" 试：第二条支路会在残留路径上继续追加，产出长度大于 2 的字符串，结果集彻底错乱。

错误写法：递归出口写成 idx > s.length()。会多走一层并在 s.charAt(idx) 处下标越界。

错误写法：用 Set 收结果来「保险」。本题不同选择必然产出不同串，去重毫无必要；更糟的是它会掩盖前两条那类重复分支的 bug，让真正的建模错误查不出来。

错误写法：改用 new StringBuilder(path.substring(0, idx)) 之类的方式做回退。功能正确，但每层都复制一次字符串，总开销从 $O(2^k n)$ 涨到 $O(2^k n^2)$。

错误写法：改用位掩码枚举时，把掩码的第 i 位对应到「字符串第 i 个字符」而不是「第 i 个字母」。用 s = "a1b" 试：需要 3 位掩码却只有 2 个字母，8 种组合里一半是重复的。

相似题目

题目	难度	考察点
17. 电话号码的字母组合	中等	每位的选择集来自数字到字母的映射，分支数不等
22. 括号生成	中等	同为每步二选一，但要靠左右括号计数剪掉非法路径
46. 全排列	中等	真正的排列问题，选择集是剩余元素、逐层递减
78. 子集	中等	同样每位选或不选，但每个内部节点也是答案
1087. 花括号展开	中等	选择集由输入显式列出，还要求结果按字典序