leetcode784题：字母大小写全排列

题目描述：

给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。

示例：
输入：S = "a1b2"
输出：["a1b2", "a1B2", "A1b2", "A1B2"]

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

输入：S = "12345"
输出：["12345"]

解题思路：

根据题目描述，先画出递归树，如下图所示。可知这道题为一个二叉树。二叉树问题一般可以用DFS即深度优先遍历算法来解决，即可以用回溯算法。代入回溯算法的代码模板即可。

PS：注意每个分结点只有两种状态，故需要for循环。

字母大小写转化技巧：

我们发现大写字符与其对应的小写字符的 ASCII 的差为 32，32 这个值如果敏感的话，它是 2^5=32.在编程语言中，可以表示为 1 << 5。而

变换大小写这件事等价于：

如果字符是小写字符，减去 32 得到大写字符；
如果字符是大写字符，加上 32 得到小写字符。
而这两者合并起来，就是给这个字符做一次不进位的加法，即异或上 1 << 5。

Java代码

  

   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     
    public List<String> letterCasePermutation(String S) {
     
    
   

    

     

    
    

     

              List<String> res=new ArrayList<>();
     
    
   

    

     

    
    

     
        int len=S.length();
     
    
   

    

     

    
    

     
        if(len==0){
     
    
   

    

     

    
    

     
            return res;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        char[] chararray=S.toCharArray();
     
    
   

    

     

    
    

     

              dfs(0,chararray,res);
     
    
   

    

     

    
    

     
        return res;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    public void dfs(int startIndex,char[] chararray,List<String> res){
     
    
   

    

     

    
    

     
        if(startIndex==chararray.length){
     
    
   

    

     

    
    

     

                  res.add(new String(chararray));
     
    
   

    

     

    
    

     
            return;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

              dfs(startIndex+1,chararray,res); //如果是数字就跳过判断，直接递归
     
    
   

    

     

    
    

     
        if(Character.isLetter(chararray[startIndex])){
     
    
   

    

     

    
    

     

                  chararray[startIndex]^=1<<5; //大小写转换技巧
     
    
   

    

     

    
    

     

                  dfs(startIndex+1,chararray,res);
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：小小谢先生，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/xiewenrui1996/article/details/112846869