784. 字母大小写全排列 - Letter Case Permutation

🎯 问题描述（来源于LeetCode）

描述：
给定一个字符串 s，通过将字符串中的每个字母转变大小写，我们可以获得一个新的字符串。
返回所有可能得到的字符串集合。
答案可以按任意顺序返回。

说明：

字母以外的字符（数字）保持不变。
大小写转换仅针对英文字母。

示例：

示例 1：

1 2	输入: s = "a1b2" 输出: ["a1b2", "a1B2", "A1b2", "A1B2"]

示例 2：

1 2	输入: s = "3z4" 输出: ["3z4", "3Z4"]

💻 解题思路

思路：回溯法（DFS）

算法步骤

将字符串 s 转换为字符列表 path（便于原地修改）。
定义递归函数 dfs(i)，表示当前处理到第 i 个字符：
- 如果 i == n，将当前 path 拼接成字符串加入答案列表，返回。
- 如果当前字符 path[i] 是字母：
  - 先将其转为小写，递归 dfs(i+1)；
  - 再将其转回大写，递归 dfs(i+1)。
- 如果是数字，则直接递归 dfs(i+1)（无需分支）。
从 dfs(0) 开始搜索。
返回答案列表。

代码实现

from typing import List

class Solution:
    def letterCasePermutation(self, s: str) -> List[str]:
        ans = []
        n = len(s)
        path = list(s)  # 转成字符列表便于修改

        def dfs(i):
            if i == n:
                ans.append("".join(path))
                return
            if path[i].isalpha():
                # 分支1：小写
                path[i] = path[i].lower()
                dfs(i + 1)
                # 分支2：大写
                path[i] = path[i].upper()
                dfs(i + 1)
            else:
                dfs(i + 1)

        dfs(0)
        return ans

📊 性能分析

时间复杂度： $O(2^k \cdot n)$ ，其中 $k$ 是字符串中字母的数量。每个字母产生两个分支，最终有 $2^k$ 个结果，构造每个结果需要 $O(n)$ 时间。
空间复杂度： $O(n)$ ，递归栈深度为 $n$ ，加上路径数组 path 和结果存储（不计输出空间）。

思考

该回溯解法利用了 DFS 枚举所有大小写组合，代码简洁高效。通过将字符串转换为列表实现原地修改，避免了频繁的字符串拼接，同时利用 isalpha() 判断字母，lower()/upper() 转换大小写，逻辑清晰。需要注意的是，每次递归修改 path[i] 后，在另一分支前必须显式改回另一大小写（或使用临时变量），这里先小写再大写，保证了两种状态都能正确探索。如果字符串中包含大量字母， $2^k$ 可能爆炸，但题目数据范围通常较小，此方法完全可行。