字母大小写全排列如何用回溯生成？数字字符为什么直接跳过？

简化版

字母大小写全排列可以把每个字符看成一个决策点。

如果是数字，它没有大小写分支，直接加入路径；如果是字母，就分成小写和大写两个分支。

递归走到字符串末尾时，把当前路径加入答案。

详细版

回溯状态可以定义为：正在处理下标 index，当前已经构造出的字符数组是 path。

每次看 s[index]：

如果是数字，只能选择原字符；
如果是字母，可以选择 toLowerCase() 或 toUpperCase()。

递归深度等于字符串长度。假设字母个数是 L，结果数量是 2^L，所以时间复杂度至少是 O(n * 2^L)，因为每个结果都要构造长度为 n 的字符串。

这题重点不是剪枝，而是把字符选择树讲清楚。

完整版教学

一、为什么这是回溯问题

题目要输出所有可能字符串，而不是判断是否存在一个答案。每个字母位置都有两种选择，数字位置只有一种选择，所有选择组合起来就是一棵状态树。回溯适合这种“逐位做选择、走到底收集结果”的枚举问题。

记忆钩子：看到“生成所有可能结果”，先想状态树；每个位置就是一层决策。

二、状态树长什么样

以 a1b 为例：

index=0: a/A
index=1: 1
index=2: b/B
结果: a1b, a1B, A1b, A1B

数字 1 不产生分叉，只是路径中的固定字符。字母位置产生两条边，最终叶子节点就是完整字符串。

三、递归参数怎么设计

最自然的递归参数是 index 和 path。index 表示处理到哪里，path 保存已经选择的字符。每进入下一层，就处理下一个字符；当 index === s.length 时，说明路径完整，可以加入答案。

参数	含义	为什么需要
`index`	当前处理位置	控制递归深度
`path`	已构造字符	形成最终字符串
`ans`	所有结果	收集叶子节点

这三个变量足够描述整个搜索过程。

四、代码模板

实现如下：

function letterCasePermutation(s) {
  const ans = []
  const path = []

  function dfs(index) {
    if (index === s.length) {
      ans.push(path.join(''))
      return
    }
    const ch = s[index]
    if (/[0-9]/.test(ch)) {
      path.push(ch)
      dfs(index + 1)
      path.pop()
    } else {
      path.push(ch.toLowerCase())
      dfs(index + 1)
      path.pop()
      path.push(ch.toUpperCase())
      dfs(index + 1)
      path.pop()
    }
  }

  dfs(0)
  return ans
}

如果想避免正则，也可以用字符码判断是否为字母。

五、复杂度为什么和字母数有关

不是每个字符都产生两种选择，只有字母产生分叉。如果字符串长度是 n，字母数量是 L，叶子节点数量就是 2^L。每个叶子需要构造长度为 n 的字符串，所以输出成本是：

O(n * 2^L)

空间上递归深度是 O(n)，答案数组不计入额外空间时通常只看路径和调用栈。

六、常见误区与追问

误区：数字字符也分支。 数字没有大小写，分支会产生重复结果。
误区：忘记 path.pop()。 回溯不撤销选择，后续分支会污染路径。
误区：把字符串频繁拼接。 可以拼接，但字符数组路径更容易展示回溯过程。
追问：结果数量为什么不是 2^n？ 只有字母产生两种选择，数字只有一种。
追问：能否用 BFS？ 可以逐字符扩展结果集，本质仍是在遍历同一棵状态树。

这些点说明你是否理解“选择空间”而不是机械套模板。

七、加强记忆

字母大小写全排列记成“数字单路走，字母分两叉”。递归层数等于字符串长度，叶子节点是完整结果。回溯的动作就是选择一个字符、递归下一位、撤销选择。复杂度由字母数量决定，因为只有字母才让状态树翻倍。

简化版

详细版