字母大小写全排列

此题解采用了回溯算法。主要思路是遍历给定字符串s的每个字符，如果字符是字母，则有两个选择：小写形式和大写形式。对于每个字母，都递归地探索这两种可能性。如果字符是数字，则无需改变，直接添加到当前字符串，并继续处理下一个字符。当递归到字符串末尾时，将当前构建的字符串添加到结果列表中。这种方法系统地探索了所有可能的字母大小写组合，从而生成所有可能的字符串。

时间复杂度: O(2^n)

空间复杂度: O(2^n * n)

from typing import List

class Solution:
    def letterCasePermutation(self, s: str) -> List[str]:
        def backtrack(string, index, current):
            # 如果已经处理完整个字符串，将当前结果添加到结果列表中
            if index == len(string):
                results.append(current)
                return
            
            # 获取当前字符
            char = string[index]
            # 如果是字母，则生成两个分支：小写和大写
            if char.isalpha():
                backtrack(string, index + 1, current + char.lower())
                backtrack(string, index + 1, current + char.upper())
            else:
                # 如果不是字母，则直接添加到当前结果中并继续下一个字符
                backtrack(string, index + 1, current + char)
        
        # 存储所有可能字符串的结果列表
        results = []
        # 从索引0开始回溯
        backtrack(s, 0, "")
        # 返回结果列表
        return results

# 示例测试
solution = Solution()
print(solution.letterCasePermutation("a1b2"))  # 输出: ["a1b2", "a1B2", "A1b2", "A1B2"]
print(solution.letterCasePermutation("3z4"))   # 输出: ["3z4", "3Z4"]