LeetCode 784中等回溯
字母大小写全排列 图解题解
这道题到底在问什么
给定字符串 s（只含字母和数字）。每个字母都可取小写或大写两种形态，数字只有一种形态。返回所有可能的字符串，顺序不限。
- 输入
- s="a1b2"
- 输出
- "a1b2","a1B2","A1b2","A1B2"
- 输入
- s="3z4"
- 输出
- "3z4","3Z4"
最优解：一步一步想明白
- 3记住「数字一支、字母两支、走到底就收一个结果」，下面每帧都在套它。
- 4从第 0 位开始 DFS开局还没固定任何一位，结果集为空。DFS 从第 0 位 “a” 开始，逐位往右决策。
- 5固定第 0 位 = a第 0 位 “A/a” 是字母，分两支。先走小写支：把它固定成 “a”，再往第 1 位走。
- 6固定第 1 位 = 1第 1 位 “1” 是数字，只有一种形态，没有分支。原样固定后直接走第 2 位。
- 7固定第 2 位 = b第 2 位 “B/b” 是字母，分两支。先走小写支：把它固定成 “b”，再往第 3 位走。
- 8固定第 3 位 = 2第 3 位 “2” 是数字，只有一种形态，没有分支。原样固定后直接走第 4 位。
- 9第 4 位 = 终点下标走到 4，等于字符串长度，说明四位全部固定好了，当前拼出的是 “a1b2”，这条路径到底了。
- 10收入 a1b2把 “a1b2” 收进答案，现在已收集 1 个。接着回溯，去试还没走过的分支。
- 11改固定第 2 位 = B小写这一支的所有结果都收完了，回溯到第 2 位换大写支：把它改固定成 “B”，再往第 3 位走。
- 12固定第 3 位 = 2第 3 位 “2” 是数字，只有一种形态，没有分支。原样固定后直接走第 4 位。
- 13第 4 位 = 终点下标走到 4，等于字符串长度，说明四位全部固定好了，当前拼出的是 “a1B2”，这条路径到底了。
- 14收入 a1B2把 “a1B2” 收进答案，现在已收集 2 个。接着回溯，去试还没走过的分支。
- 15改固定第 0 位 = A小写这一支的所有结果都收完了，回溯到第 0 位换大写支：把它改固定成 “A”，再往第 1 位走。
- 16固定第 1 位 = 1第 1 位 “1” 是数字，只有一种形态，没有分支。原样固定后直接走第 2 位。
- 17固定第 2 位 = b第 2 位 “B/b” 是字母，分两支。先走小写支：把它固定成 “b”，再往第 3 位走。
- 18固定第 3 位 = 2第 3 位 “2” 是数字，只有一种形态，没有分支。原样固定后直接走第 4 位。
- 19第 4 位 = 终点下标走到 4，等于字符串长度，说明四位全部固定好了，当前拼出的是 “A1b2”，这条路径到底了。
- 20收入 A1b2把 “A1b2” 收进答案，现在已收集 3 个。接着回溯，去试还没走过的分支。
- 21改固定第 2 位 = B小写这一支的所有结果都收完了，回溯到第 2 位换大写支：把它改固定成 “B”，再往第 3 位走。
- 22固定第 3 位 = 2第 3 位 “2” 是数字，只有一种形态，没有分支。原样固定后直接走第 4 位。
- 23第 4 位 = 终点下标走到 4，等于字符串长度，说明四位全部固定好了，当前拼出的是 “A1B2”，这条路径到底了。
- 24收入 A1B2把 “A1B2” 收进答案，现在已收集 4 个。这是最后一个，答案已经集满。收完后 DFS 沿递归栈逐层返回，沿途已没有新的分支可换，整棵决策树到此结束。
- 25共 4 个决策树全部走完：a 两支 × b 两支 = 4 条到底的路径，对应 4 个结果。数字 1、2 始终不变。
⚠️ 容易写错的地方
✗ 错：对数字也分两支
✓ 对：只有字母才分小写/大写两支
数字没有大小写，硬分会产生重复结果
✗ 错：换大写支前忘了已经回溯到第 i 位
✓ 对：靠递归返回后原地改同一位即可
若没回到第 i 位就改，会破坏前缀
✗ 错：用 isupper 判断是否字母
✓ 对：要判「是不是字母」，用 isalpha / isLetter
小写字母也是字母，isupper 会漏掉它们
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def letterCasePermutation(self, s: str) -> List[str]:
ans = []
chars = list(s)
def dfs(i):
if i == len(chars):
ans.append(''.join(chars)); return
if chars[i].isalpha():
chars[i] = chars[i].lower(); dfs(i + 1)
chars[i] = chars[i].upper(); dfs(i + 1)
else:
dfs(i + 1)
dfs(0)
return ansC++
#include <cctype>
#include <functional>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
vector<string> letterCasePermutation(string s) {
vector<string> ans;
function<void(int)> dfs = [&](int i) {
if (i == (int)s.size()) { ans.push_back(s); return; }
if (isalpha(s[i])) {
s[i] = tolower(s[i]); dfs(i + 1);
s[i] = toupper(s[i]); dfs(i + 1);
} else dfs(i + 1);
};
dfs(0);
return ans;
}
};Java
import java.util.*;
class Solution {
List<String> ans;
char[] chars;
public List<String> letterCasePermutation(String s) {
ans = new ArrayList<>(); chars = s.toCharArray();
dfs(0);
return ans;
}
private void dfs(int i) {
if (i == chars.length) { ans.add(new String(chars)); return; }
if (Character.isLetter(chars[i])) {
chars[i] = Character.toLowerCase(chars[i]); dfs(i + 1);
chars[i] = Character.toUpperCase(chars[i]); dfs(i + 1);
} else dfs(i + 1);
}
}复杂度
时间
O(2^L · n)
L 为字母个数，叶子(完整结果)有 2^L 个；每片叶子拼一个长度 n 的字符串需 O(n)
空间
O(2^L · n)
存所有结果就要这么多；递归栈深 O(n)，相对结果集可忽略
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 字母大小写全排列 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
不用递归，能怎么生成所有结果？+
可以迭代：维护一个结果列表，初始只有空串。逐位扫描，数字位就把每个已有结果都接上这个数字；字母位就把每个已有结果分别接上小写和大写两份，列表规模翻倍。最终列表就是全部结果，本质和 DFS 等价。
若只要结果的个数，不要具体字符串，怎么算？+
只需统计字母个数 L，答案就是 2^L，O(n) 一遍扫描即可，不必真的展开所有排列，避免指数级开销。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 字母大小写全排列 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。