题目描述
思路解析动画文字版
记住「数字一支、字母两支、走到底就收一个结果」，下面每帧都在套它。
准备 · 空前缀：开局还没固定任何一位，结果集为空。DFS 从第 0 位 “a” 开始，逐位往右决策。
第 0 位 · 字母 → 小写：第 0 位 “A/a” 是字母，分两支。先走小写支：把它固定成 “a”，再往第 1 位走。
第 1 位 · 数字：第 1 位 “1” 是数字，只有一种形态，没有分支。原样固定后直接走第 2 位。
第 2 位 · 字母 → 小写：第 2 位 “B/b” 是字母，分两支。先走小写支：把它固定成 “b”，再往第 3 位走。
第 3 位 · 数字：第 3 位 “2” 是数字，只有一种形态，没有分支。原样固定后直接走第 4 位。
抵达末尾 · a1b2：下标走到 4，等于字符串长度，说明四位全部固定好了，当前拼出的是 “a1b2”，这条路径到底了。
收获 · a1b2：把 “a1b2” 收进答案，现在已收集 1 个。接着回溯，去试还没走过的分支。
第 2 位 · 字母 → 大写：小写这一支的所有结果都收完了，回溯到第 2 位换大写支：把它改固定成 “B”，再往第 3 位走。
第 3 位 · 数字：第 3 位 “2” 是数字，只有一种形态，没有分支。原样固定后直接走第 4 位。
抵达末尾 · a1B2：下标走到 4，等于字符串长度，说明四位全部固定好了，当前拼出的是 “a1B2”，这条路径到底了。
收获 · a1B2：把 “a1B2” 收进答案，现在已收集 2 个。接着回溯，去试还没走过的分支。
第 0 位 · 字母 → 大写：小写这一支的所有结果都收完了，回溯到第 0 位换大写支：把它改固定成 “A”，再往第 1 位走。
第 1 位 · 数字：第 1 位 “1” 是数字，只有一种形态，没有分支。原样固定后直接走第 2 位。
第 2 位 · 字母 → 小写：第 2 位 “B/b” 是字母，分两支。先走小写支：把它固定成 “b”，再往第 3 位走。
第 3 位 · 数字：第 3 位 “2” 是数字，只有一种形态，没有分支。原样固定后直接走第 4 位。
抵达末尾 · A1b2：下标走到 4，等于字符串长度，说明四位全部固定好了，当前拼出的是 “A1b2”，这条路径到底了。
收获 · A1b2：把 “A1b2” 收进答案，现在已收集 3 个。接着回溯，去试还没走过的分支。
第 2 位 · 字母 → 大写：小写这一支的所有结果都收完了，回溯到第 2 位换大写支：把它改固定成 “B”，再往第 3 位走。
第 3 位 · 数字：第 3 位 “2” 是数字，只有一种形态，没有分支。原样固定后直接走第 4 位。
抵达末尾 · A1B2：下标走到 4，等于字符串长度，说明四位全部固定好了，当前拼出的是 “A1B2”，这条路径到底了。
收获 · A1B2：把 “A1B2” 收进答案，现在已收集 4 个。这是最后一个，答案已经集满。收完后 DFS 沿递归栈逐层返回，沿途已没有新的分支可换，整棵决策树到此结束。
完成 · 全部 4 个结果：决策树全部走完：a 两支 × b 两支 = 4 条到底的路径，对应 4 个结果。数字 1、2 始终不变。
边界先想清：没有字母时只返回原串本身；有 L 个字母就返回 2^L 个。
面试可延伸：迭代翻倍写法、以及只求个数时的 2^L 快捷算法。
参考代码
from typing import Listclass 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 ans复杂度
- 时间：O(2^L · n)，L 为字母个数，叶子(完整结果)有 2^L 个；每片叶子拼一个长度 n 的字符串需 O(n)
- 空间：O(2^L · n)，存所有结果就要这么多；递归栈深 O(n)，相对结果集可忽略
易错点
面试追问把动画讲成自己的话
追问不用递归，能怎么生成所有结果？
追问若只要结果的个数，不要具体字符串，怎么算？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
黄金矿工
LeetCode 1219 · 中等 · 沿着 回溯套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题