LeetCode 784 字母大小写全排列Letter Case PermutationGo 双解法深度解析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 784「字母大小写全排列」Letter Case Permutation展开以 LeetCode-Go 仓库中 leetcode/0784.Letter-Case-Permutation 的题解为核心深入拆解 DFS 深搜与迭代翻倍两种解法的完整实现、字符大小写转换的底层原理以及测试用例的验证方式。读完本文你将掌握如何枚举字符串中所有字母的大小写组合、如何用组合数思想剪枝回溯以及 ASCII 码差在大小写转换中的高效运用。题目描述给定一个字符串S我们可以将其中每一个字母单独转换为小写或大写从而构造出新的字符串。请返回所有可能构造出的字符串集合。示例 1 输入S a1b2 输出[a1b2, a1B2, A1b2, A1B2] 示例 2 输入S 3z4 输出[3z4, 3Z4] 示例 3 输入S 12345 输出[12345]约束条件来自 原题说明字符串S的长度介于1到12之间S仅由字母或数字组成。题目分析与思路框架本题本质是组合枚举问题字符串中的数字位置固定不变每个字母位置有两种选择小写或大写。设字符串中字母数量为m则答案数量为2^m种。当字符串全是数字时m 0答案只有原串本身一种。仓库中的题解给出了两种典型实现分别对应原文档「解题思路」中提到的 DFS 深搜与 BFS 广搜两条路线解法实现函数核心思想解法一letterCasePermutationDFS 深搜 组合选择「大写位置」解法二letterCasePermutation1迭代翻倍逐个字母扩展结果集两个函数都位于 784. Letter Case Permutation.go 中测试用例位于 784. Letter Case Permutation_test.go。解法一DFS 深搜——从组合数角度剪枝思路先看一个关键观察每个字母只有「保持小写」和「变成大写」两种状态等价于从所有字母位置中选出若干位置将其大写化。于是问题转化为对字符串中m个字母位置依次枚举选择0个、1个、…、m个位置大写并将每种选择组合落地为具体字符串。这样就把「排列枚举」规约成了经典的组合搜索天然可以用 DFS 实现且枚举过程中可以提前剪枝。源码实现拆解// 解法一DFS 深搜 func letterCasePermutation(S string) []string { if len(S) 0 { return []string{} } res, pos, c : []string{}, []int{}, []int{} SS : strings.ToLower(S) for i : 0; i len(SS); i { if isLowerLetter(SS[i]) { pos append(pos, i) } } for i : 0; i len(pos); i { findLetterCasePermutation(SS, pos, i, 0, c, res) } return res }代码逻辑分三步统一转小写strings.ToLower(S)把输入统一成小写形式SS。这一步非常巧妙——原输入可能混有大写如测试用例中的mQe统一小写后后续只需关心「哪些字母位置要被改回大写」避免了大小写混合带来的分支判断。收集字母位置遍历SS用isLowerLetter判断是否为a~z把字母的下标存入pos切片。按大写数量分批 DFSfor i : 0; i len(pos); i枚举要大写化的字母个数target从 0 到全部字母数调用组合搜索函数逐个生成结果。组合搜索的核心函数func findLetterCasePermutation(s string, pos []int, target, index int, c []int, res *[]string) { if len(c) target { b : []byte(s) for _, v : range c { b[pos[v]] - a - A } *res append(*res, string(b)) return } for i : index; i len(pos)-(target-len(c))1; i { c append(c, i) findLetterCasePermutation(s, pos, target, i1, c, res) c c[:len(c)-1] } }终止条件已选中的大写位置数量len(c)达到目标值target时把c中记录的每个位置pos[v]对应的字符改为大写生成一个完整结果。剪枝边界i len(pos)-(target-len(c))1保证剩余可选位置足够凑满target个避免无效递归。回溯c append(c, i)后递归c c[:len(c)-1]撤销选择恢复现场是标准组合模板。大小写转换的底层原理func isLowerLetter(v byte) bool { if v a v z { return true } return false }两个关键点判断字母不依赖任何标准库直接利用 ASCII 码范围a~z、A~Z连续分布的特性大小写转换同样利用 ASCII 码差小写字母与大写字母在 ASCII 表中恰好相差 32即a - A 32。因此b[pos[v]] - a - A等价于把该字符的 ASCII 码减去 32一步完成小写到大写的转换比调用strings.ToUpper更贴近底层、更高效。以a1b2为例统一小写后为a1b2字母位置为[0, 2]。依次枚举大写0、1、2个位置选 0 个a1b2选 1 个A1b2、a1B2选 2 个A1B2恰好覆盖全部 4 种结果。解法二迭代翻倍——BFS 思路的简洁表达思路解法二走的是广度优先/逐层扩展路线初始结果集只含全小写串遍历到第一个字母时为结果集中的每个字符串生成一个「该字母大写」的变体结果集翻倍继续处理后续字母每处理一个字母结果集就翻倍一次。最终结果集大小恒为2^m。源码注释中给出了mqe的翻倍过程第一步[mqe] - [mqe, Mqe] 第二步[mqe, Mqe] - [mqe, Mqe, mQe, MQe] 第三步[mqe, Mqe, mQe, MQe] - [mqe, Mqe, mQe, MQe, mqE, MqE, mQE, MQE]每处理一个字母已有结果整体复制一遍新复制的部分把该字母改为大写。源码实现拆解func letterCasePermutation1(S string) []string { res : make([]string, 0, 1uint(len(S))) S strings.ToLower(S) for k, v : range S { if isLetter784(byte(v)) { switch len(res) { case 0: res append(res, S, toUpper(S, k)) default: for _, s : range res { res append(res, toUpper(s, k)) } } } } if len(res) 0 { res append(res, S) } return res }几个值得注意的实现细节预分配容量make([]string, 0, 1uint(len(S)))直接以2^len(S)作为容量上限预分配避免扩容带来的内存拷贝。首字母特殊处理处理第一个字母时结果集为空len(res) 0此时直接追加S与其大写变体两个字符串后续字母则在已有结果之上逐条追加大写变体for _, s : range res遍历时持续 append天然形成翻倍。全数字兜底若整个字符串没有字母如12345res始终为空最后append(res, S)返回原串。辅助函数与解法一同一套 ASCII 技巧func isLetter784(c byte) bool { return (c a c z) || (c A c Z) } func toUpper(s string, i int) string { b : []byte(s) b[i] - a - A return string(b) }注意解法二也先把S转为小写再逐个把指定下标的字符通过- a - A变大写因此对mQe这类含大写字母的输入同样适用。测试用例与验证仓库在 784. Letter Case Permutation_test.go 中通过表驱动测试覆盖了 6 组用例基本涵盖了本题的所有边界输入期望输出覆盖点mQe8 种全排列输入含大写字母验证统一小写预处理C[c, C]单字母字符串m 1a1b24 种全排列官方示例字母与数字混合3z4[3z4, 3Z4]官方示例单字母 数字12345[12345]全数字m 0结果集只有原串[]空串边界由解法一的len(S) 0分支兜底从测试代码可以看到Test_Problem784对每组用例同时调用了letterCasePermutation(p.one)与letterCasePermutation1(p.one)两个版本前者结果用于打印输出即同一份测试数据同时验证了 DFS 与迭代翻倍两种实现的一致性。这也印证了原文档「DFS 深搜或者 BFS 广搜都可以」的结论——两条路线殊途同归。复杂度分析与对比设字符串长度为n其中字母数量为m解法一DFS 组合搜索时间复杂度O(2^m × n)。共枚举2^m种大写组合每种组合生成字符串需要O(n)的字符数组拷贝与修改空间复杂度O(2^m × n)用于存放结果递归深度不超过O(m)回溯栈开销可忽略。解法二迭代翻倍时间复杂度O(2^m × n)。每处理一个字母需遍历当前结果集大小为2^已处理字母数并复制字符串总复制次数为1 2 4 … 2^(m-1) 2^m - 1空间复杂度O(2^m × n)存放结果同时预分配容量避免了中间扩容开销。两种解法在最坏情况下全部是字母、n 12均需生成2^12 4096个长度为 12 的结果时空开销在本题约束下完全可控。实际选择时解法一逻辑更贴近「组合枚举」的数学本质便于扩展到其他组合类题目解法二代码更短、实现更直观且预分配容量的写法在工程上更省心。小结通过 LeetCode 784可以一次性巩固三个高频考点回溯/DFS 模板findLetterCasePermutation是组合搜索的标准骨架——终止条件、剪枝边界、选入与撤销三步缺一不可ASCII 码运算b[i] - a - A利用大小写字母 ASCII 码差 32 的特性完成转换是位运算之外的另一种高效字符处理范式枚举思想迁移本题的数字位置固定、字母位置二选一是「子集枚举」类问题的典型代表解法二本质上就是子集生成中「逐位翻倍」思路的变体。深入阅读仓库内 784. Letter Case Permutation.go 的完整实现与 对应测试可以继续对比两种写法在边界处理空串、全数字、含大写输入上的差异从而在实际面试中根据题目变体灵活选用最合适的实现。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考