LeetCode784. 字母大小写全排列

ゝ一世哀愁。 2022-02-17 11:36 174阅读 0赞

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

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

思路是：  
找出不同的序列，我自己的边界条件判断是没有问题的，还有参数，边界条件下需要一个List,所以if判断条件下，list.add()所以参数一个List<String> list.而每次的char\[\] 只是让本身的序列变成大写或小写去尝试，如果是大写，便深度递归下去，直至有解便有出口，回溯的点在哪里，如果大写行不通，那么便尝试小写，同时不像是深度遍历那样，访问过了便后续都不允许访问，回溯是，按照顺序，有过程的遍历所有的解空间树，当前行不通的时候，便回溯到上一级，这个是递归能实现的，但是，更重要的是c\[n\]=a;重新把数据变回。

回溯从下一层递归不能继续下去的时候，这个会重新令当前的从c\[n\]=a;重新把当前的解换成另外一个可行解，回溯法的意义是，递归返回不是重点，而是返回后重新改变当前的解，使解重新可行

使用回溯法解决问题，还是得实际情况实际分析才对。

代码：

public List<String> letterCasePermutation(String S) {
    
          List<String> result = new ArrayList<>();
    
          char[] c = S.toCharArray();
    
          int len = S.length();
    
          persut(result,c,0);
    
            return result;
    
    
        }
    
    
    
        public void persut(List<String> list,char[] c,int n){
    
            if(n==4){
                //分情况讨论，它这里不用操纵数组具体得情况
                list.add(new String(c));
    
                return;
            }
            //new
    
            //我为什么想到用数组遍历，因为之前的8皇后的情况，让我遍历.
            //但是这里应该是具体情况具体分析
                char a = c[n];
                if(a>='a'&&a<='z'){//字符就深度遍历
    
                    c[n]=(char)(a-32);//大写
                    persut(list,c,n+1);//从大写这里深度递归
                    //回溯
                    c[n]=a;
    
                }else if(a>='A'&&a<='Z'){
                    c[n]=(char)(a+32);
                    persut(list,c,n+1);
                    c[n]=a;
    
    
            }
                //这里是回溯的情况下遍历另外的情况
            //同样是n+1
            persut(list,c,n+1);
    
    
    
        }