算法题 字母大小写全排列

字母大小写全排列

问题描述

给定一个字符串s，通过将字符串中的每个字母改成大写或小写，生成所有可能的字符串。

返回所有可能的字符串组成的列表。数字和特殊字符保持不变。

示例：

输入: s = "a1b2" 输出: ["a1b2", "a1B2", "A1b2", "A1B2"] 输入: s = "3z4" 输出: ["3z4", "3Z4"] 输入: s = "12345" 输出: ["12345"]

算法思路

核心：

1. 字符：只有字母需要考虑大小写变化，数字和特殊字符保持不变
2. 选择：每个字母有2种选择（大写或小写），如果有k个字母，总共有2^k种排列

方法：

• 回溯：递归处理每个位置，遇到字母时尝试两种大小写
• 迭代：从空结果开始，逐个字符扩展所有可能的结果
• 位运算：用二进制位表示每个字母的选择（0=小写，1=大写）

代码实现

方法一：回溯

importjava.util.*;classSolution{/** * 使用回溯生成字母大小写全排列 * * @param s 输入字符串 * @return 所有可能的字符串列表 */publicList<String>letterCasePermutation(Strings){List<String>result=newArrayList<>();// 将字符串转换为字符数组char[]chars=s.toCharArray();// 从索引0开始回溯backtrack(chars,0,result);returnresult;}/** * 回溯函数：递归生成所有可能的排列 * * @param chars 当前字符数组 * @param index 当前处理的字符索引 * @param result 结果列表 */privatevoidbacktrack(char[]chars,intindex,List<String>result){// 递归终止条件：处理完所有字符if(index==chars.length){result.add(newString(chars));return;}charcurrent=chars[index];if(Character.isLetter(current)){// 1：保持小写（或原样）chars[index]=Character.toLowerCase(current);backtrack(chars,index+1,result);// 2：转换为大写chars[index]=Character.toUpperCase(current);backtrack(chars,index+1,result);}else{// 非字母字符，直接跳过backtrack(chars,index+1,result);}}}

方法二：迭代

importjava.util.*;classSolution{/** * 使用迭代生成字母大小写全排列 * * @param s 输入字符串 * @return 所有可能的字符串列表 */publicList<String>letterCasePermutation(Strings){List<String>result=newArrayList<>();result.add("");// 初始化为空字符串// 逐个字符处理for(charc:s.toCharArray()){List<String>newResult=newArrayList<>();// 对当前结果中的每个字符串，扩展新的字符for(Stringstr:result){if(Character.isLetter(c)){// 字母：添加小写和大写两种情况newResult.add(str+Character.toLowerCase(c));newResult.add(str+Character.toUpperCase(c));}else{// 非字母：直接添加newResult.add(str+c);}}result=newResult;}returnresult;}}

方法三：位运算

importjava.util.*;classSolution{/** * 使用位运算生成字母大小写全排列 * * @param s 输入字符串 * @return 所有可能的字符串列表 */publicList<String>letterCasePermutation(Strings){// 首先找出所有字母的位置List<Integer>letterIndices=newArrayList<>();char[]chars=s.toCharArray();for(inti=0;i<chars.length;i++){if(Character.isLetter(chars[i])){letterIndices.add(i);}}intletterCount=letterIndices.size();List<String>result=newArrayList<>();// 枚举所有可能的位组合 (0 到 2^letterCount - 1)for(intmask=0;mask<(1<<letterCount);mask++){char[]current=Arrays.copyOf(chars,chars.length);// 根据mask的每一位决定对应字母的大小写for(inti=0;i<letterCount;i++){if((mask&(1<<i))!=0){// 第i位为1：大写current[letterIndices.get(i)]=Character.toUpperCase(current[letterIndices.get(i)]);}else{// 第i位为0：小写current[letterIndices.get(i)]=Character.toLowerCase(current[letterIndices.get(i)]);}}result.add(newString(current));}returnresult;}}

算法分析

• 时间复杂度：O(2^n × m)

  • n = 字符串中字母的个数
  • m = 字符串总长度
  • 共有2^n种排列，每种排列需要O(m)时间构建

• 空间复杂度：

  • 回溯：O(m) - 递归深度为m，不包括结果存储
  • 迭代：O(2^n × m) - 需要存储所有中间结果
  • 位运算：O(2^n × m) - 需要存储所有结果

算法过程

s = “a1b2”

回溯：

开始: index=0, chars=['a','1','b','2'] ├─ index=0, 'a'是字母 │ ├─ 小写: chars=['a','1','b','2'], index=1 │ │ ├─ index=1, '1'不是字母 → index=2 │ │ │ ├─ index=2, 'b'是字母 │ │ │ │ ├─ 小写: chars=['a','1','b','2'], index=3 │ │ │ │ │ └─ index=3, '2'不是字母 → index=4 → 添加"a1b2" │ │ │ │ └─ 大写: chars=['a','1','B','2'], index=3 │ │ │ │ └─ index=3, '2'不是字母 → index=4 → 添加"a1B2" │ │ └─ 大写: chars=['A','1','b','2'], index=1 │ ├─ index=1, '1'不是字母 → index=2 │ │ ├─ index=2, 'b'是字母 │ │ │ ├─ 小写: chars=['A','1','b','2'], index=3 → 添加"A1b2" │ │ │ └─ 大写: chars=['A','1','B','2'], index=3 → 添加"A1B2"

最终结果：[“a1b2”, “a1B2”, “A1b2”, “A1B2”]

迭代：

• 初始：[“”]
• 处理’a’：[“a”, “A”]
• 处理’1’：[“a1”, “A1”]
• 处理’b’：[“a1b”, “a1B”, “A1b”, “A1B”]
• 处理’2’：[“a1b2”, “a1B2”, “A1b2”, “A1B2”]

测试用例

publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准示例System.out.println("Test 1: "+solution.letterCasePermutation("a1b2"));// ["a1b2", "a1B2", "A1b2", "A1B2"]// 测试用例2：包含数字System.out.println("Test 2: "+solution.letterCasePermutation("3z4"));// ["3z4", "3Z4"]// 测试用例3：纯数字System.out.println("Test 3: "+solution.letterCasePermutation("12345"));// ["12345"]// 测试用例4：单个字母System.out.println("Test 4: "+solution.letterCasePermutation("a"));// ["a", "A"]// 测试用例5：空字符串System.out.println("Test 5: "+solution.letterCasePermutation(""));// [""]// 测试用例6：多个连续字母System.out.println("Test 6: "+solution.letterCasePermutation("ab"));// ["ab", "aB", "Ab", "AB"]// 测试用例7：包含大写字母的输入System.out.println("Test 7: "+solution.letterCasePermutation("A1B2"));// ["a1b2", "a1B2", "A1b2", "A1B2"]// 测试用例8：混合大小写和特殊字符System.out.println("Test 8: "+solution.letterCasePermutation("C1@d"));// ["c1@d", "c1@D", "C1@d", "C1@D"]// 测试用例9：较长字符串System.out.println("Test 9: "+solution.letterCasePermutation("a1b2c3"));// 8种组合// 测试用例10：只有特殊字符System.out.println("Test 10: "+solution.letterCasePermutation("!@#$%"));// ["!@#$%"]}

关键点

1. 字符：

   • 使用Character.isLetter()准确判断字母
   • 包含所有Unicode字母，不仅仅是a-z和A-Z

2. 大小写转换：

   • 使用Character.toLowerCase()和Character.toUpperCase()

3. 回溯：

   • 修改字符数组时要注意状态恢复

4. 边界情况：

   • 空字符串、纯数字、纯字母等特殊情况

常见问题

1. 为什么回溯空间复杂度更低？
   • 回溯只在递归栈中存储当前路径
   • 迭代需要存储所有中间结果，空间开销大