昨天晚上十一点多吧，我在公司楼下抽烟（别学哈），我们组小李突然微信敲我：东哥，那个“字母大小写全排列”你不是老说很像线上开关么，给个能直接跑的 Python 呗，我明天面试要讲……我当时困得要死，又想起前阵子有个灰度发布，配置里有个 env=prod / env=Prod 这种鬼东西，大小写不统一导致缓存 key 命中率直接掉一截，排查半天才发现就差一个大写 P，你说气不气。
这个题其实就一个意思：给你一串字符串，里面可能有字母也可能有数字，你要把每个字母都当成“有两个形态”的开关——小写/大写，数字就别动，然后把所有组合都吐出来。就像你们做配置中心那种 feature flag，一堆开关乘起来，组合数就指数爆炸，字母有 L 个，就会有 2^L 个结果，跑起来你心里得有数，不然线上一下子搞成生成一百万条字符串，你内存就开始骂街了。
我一般写这种就用回溯，别被“回溯”吓到，就是你走到一个字符，遇到字母就分叉两条路，遇到数字就一条路，走到末尾就收集答案。你把它想成走迷宫，走到岔路口就先走左边，再退回来走右边，反正就是那个……嗯，DFS。你要是喜欢迭代也行，用一个列表当队列，每来一个字母就把现有结果复制一份换大小写，但我更喜欢递归，短，清晰，还不容易写错（当然递归深度太大也会翻车，不过这题字符串一般不长）。
代码我给小李发的就是下面这个，没抄谁的哈，写得比较“能上工位”的那种，还顺手加了个小测试，免得你们说我瞎写。
from typing import Listdefletter_case_permutation(s: str) -> List[str]:""" 字母大小写全排列： - 字母：可小写/大写 - 数字/其他字符：原样保留（题目一般只有字母数字） """ chars = list(s) n = len(chars) res: List[str] = [] path: List[str] = [''] * n # 预分配，少点拼接开销defdfs(i: int) -> None:if i == n: res.append(''.join(path))return c = chars[i]if'a' <= c <= 'z'or'A' <= c <= 'Z':# 分支1：小写 path[i] = c.lower() dfs(i + 1)# 分支2：大写 path[i] = c.upper() dfs(i + 1)else:# 数字等，只有一条路 path[i] = c dfs(i + 1) dfs(0)return resif __name__ == "__main__": print(letter_case_permutation("a1b2"))# 可能输出顺序不同，但集合一样：# ['a1b2', 'a1B2', 'A1b2', 'A1B2'] print(letter_case_permutation("3z4"))# ['3z4', '3Z4']
你看这里有个小细节，path 我没用 path + [x] 这种写法，因为那样每层都新建列表，短字符串无所谓，但你写习惯了，后面做点稍大点的组合题就开始慢得离谱。还有就是判断字母我没用 isalpha()，不是它不行哈，是有些同学字符串里混进中文、下划线啥的，isalpha() 会让你莫名其妙也分叉（当然面试题一般不会这么恶心，但线上数据我可不敢赌）。
然后你讲复杂度的时候别背公式，像聊天一样说：假设有 L 个字母，那就是每个字母两种选法，结果数 2^L，每个结果长度是 n，所以大概就是 2^L * n 这么个量级。面试官点头你就过一半了。哦对，还有个坑，很多人写 BFS 复制列表的时候会把同一个引用改来改去，最后结果全一样，这种错最丢人，你们自己注意哈。
行了我先不说了，刚刚外卖到了，等下我还得回去把那个线上日志滚动策略再改一下，不然磁盘又要爆了……
