784. 字母大小写全排列

784. 字母大小写全排列

1、路径：也就是已经做出的选择。
2、选择列表：也就是你当前可以做的选择。
3、结束条件：也就是到达决策树底层，无法再做选择的条件。

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

回溯算法

package main
import (
    "fmt"
    "strings"
    "unicode"
)
func main() {
    fmt.Println(letterCasePermutation("a1b2"))
}
func letterCasePermutation(S string) []string {
    res :=make([]string,0)
    dfs([]byte(S),0,&res)
    return res
}
func dfs(char []byte,index int,res *[]string){
    if index==len(char) {
        *res = append(*res,string(char))
        return
    }
    dfs(char,index+1,res)
    if unicode.IsLetter(rune(char[index])) {
        if unicode.IsLower(rune(char[index])) {
            char[index] = strings.ToUpper(string(char[index]))[0]
        }else {
            char[index] = strings.ToLower(string(char[index]))[0]
        }
        dfs(char,index+1,res)
    }
}

char[index] = char[index]^1<<5 异或32处理

func dfs(char []byte,index int,res *[]string){
    if index==len(char) {
        *res = append(*res,string(char))
        return
    }
    dfs(char,index+1,res)
    if unicode.IsLetter(rune(char[index])) {
        char[index] = char[index]^1<<5
        dfs(char,index+1,res)
    }
}

class Solution {
    List<String> ans = new ArrayList<>();
    int dis = 'A'-'a';
    public List<String> letterCasePermutation(String S) {
        char[] str = S.toCharArray();
        dfs(str,0);
        return ans;
    }
    /**
    *   深度优先搜索
    *   str     字符数组
    *   index   当前搜索深度
    **/
    private void dfs(char[] str,int index){
        if(index==str.length){
            ans.add(new String(str));
            return;
        }
        if(str[index]>='a'&&str[index]<='z'){//该位置为小写字母
            dfs(str,index+1);   //往下一深度搜索
            str[index]+=dis;    //字母大写
            dfs(str,index+1);   //往下一深度搜索
            str[index]-=dis;    //字母变回小写
        }else if(str[index]>='A'&&str[index]<='Z'){
            dfs(str,index+1);
            str[index]-=dis;
            dfs(str,index+1);
            str[index]+=dis;
        }else{
            dfs(str,index+1);
        }
        return;
    }
}