Medium

题目描述

给定一个字符串 s，你可以将每个字母单独转换为小写或大写来创建另一个字符串。

返回我们可以创建的所有可能字符串的列表。以任意顺序返回输出。

示例 1：

输入：s = "a1b2"
输出：["a1b2","a1B2","A1b2","A1B2"]

示例 2：

输入：s = "3z4"
输出：["3z4","3Z4"]

提示：

  • 1 <= s.length <= 12
  • s 由小写英文字母、大写英文字母和数字组成

解题思路

这道题可以用多种方法解决，主要有以下几种思路：

方法一：回溯算法（推荐） 对字符串的每个位置进行深度优先搜索。对于每个字符：

  • 如果是数字，直接跳过
  • 如果是字母，可以选择保持原样或转换大小写

递归地构建所有可能的排列，当处理完所有字符时，将结果加入答案列表。

方法二：位操作 先统计字符串中字母的个数，如果有 n 个字母，则总共有 2^n 种排列。使用位掩码枚举所有可能的大小写组合。

方法三：BFS 从原字符串开始，逐字符扩展。遇到字母时，将队列中的每个字符串分别生成大小写两个版本。

回溯算法思路清晰，代码简洁，是最直观的解法。时间复杂度为 O(n × 2^k)，其中 k 是字母个数。

代码实现

class Solution {
public:
    vector<string> letterCasePermutation(string s) {
        vector<string> result;
        backtrack(s, 0, result);
        return result;
    }
    
private:
    void backtrack(string& s, int index, vector<string>& result) {
        if (index == s.length()) {
            result.push_back(s);
            return;
        }
        
        // 保持当前字符不变
        backtrack(s, index + 1, result);
        
        // 如果是字母，尝试转换大小写
        if (isalpha(s[index])) {
            if (islower(s[index])) {
                s[index] = toupper(s[index]);
            } else {
                s[index] = tolower(s[index]);
            }
            backtrack(s, index + 1, result);
            // 回溯
            if (islower(s[index])) {
                s[index] = toupper(s[index]);
            } else {
                s[index] = tolower(s[index]);
            }
        }
    }
};

class Solution:
    def letterCasePermutation(self, s: str) -> List[str]:
        result = []
        
        def backtrack(path, index):
            if index == len(s):
                result.append(path)
                return
            
            char = s[index]
            if char.isalpha():
                # 小写版本
                backtrack(path + char.lower(), index + 1)
                # 大写版本
                backtrack(path + char.upper(), index + 1)
            else:
                # 数字直接添加
                backtrack(path + char, index + 1)
        
        backtrack("", 0)
        return result

public class Solution {
    public IList<string> LetterCasePermutation(string s) {
        IList<string> result = new List<string>();
        Backtrack(s.ToCharArray(), 0, result);
        return result;
    }
    
    private void Backtrack(char[] chars, int index, IList<string> result) {
        if (index == chars.Length) {
            result.Add(new string(chars));
            return;
        }
        
        // 保持当前字符不变
        Backtrack(chars, index + 1, result);
        
        // 如果是字母，尝试转换大小写
        if (char.IsLetter(chars[index])) {
            if (char.IsLower(chars[index])) {
                chars[index] = char.ToUpper(chars[index]);
            } else {
                chars[index] = char.ToLower(chars[index]);
            }
            Backtrack(chars, index + 1, result);
            // 回溯
            if (char.IsLower(chars[index])) {
                chars[index] = char.ToUpper(chars[index]);
            } else {
                chars[index] = char.ToLower(chars[index]);
            }
        }
    }
}

var letterCasePermutation = function(s) {
    const result = [];
    
    function backtrack(index, current) {
        if (index === s.length) {
            result.push(current);
            return;
        }
        
        const char = s[index];
        if (isNaN(char)) {
            backtrack(index + 1, current + char.toLowerCase());
            backtrack(index + 1, current + char.toUpperCase());
        } else {
            backtrack(index + 1, current + char);
        }
    }
    
    backtrack(0, "");
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度
回溯算法O(n × 2^k)O(n × 2^k)

其中 n 是字符串长度，k 是字母个数。时间复杂度中的 n 是构建每个结果字符串的开销，2^k 是所有可能排列的数量。空间复杂度包括递归栈深度 O(n) 和存储结果的空间 O(n × 2^k)。

相关题目