【亡羊補牢】挑戰資料結構與演算法第16期 LeetCode 784. 字母大小寫全排列（遞回與回溯）-有解無憂

仰望星空的人，不應該被嘲笑

題目描述

給定一個字串S，通過將字串S中的每個字母轉變大小寫，我們可以獲得一個新的字串，回傳所有可能得到的字串集合，

示例：

輸入：S = "a1b2"
輸出：["a1b2", "a1B2", "A1b2", "A1B2"]

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

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

提示：

S 的長度不超過12，
S 僅由數字和字母組成，

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/letter-case-permutation
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，

解題思路

這道題就是遞回操作，沒有回溯，是一個挺有意思的題目，在講解思路之前，我先搬運一下大佬的圖解，方便我后續補充，

參考大佬 liweiwei1419 圖解

第一步

第二步

第三步

第四步

第五步

第六步

好了，有了上述圖解之后（還是感謝大佬的圖解，萬分感謝orz），我相信明白的已經明白了，如果不明白我繼續解釋，

此題我們只需要從頭往后遍歷一遍即可，對于非字母節點，我們只會產生一個分支，而對于字母節點，我們可以產生兩個分支，即大寫字母和小寫字母，（詳細請參見下述代碼）

于是，我們只要簡單搜一遍就可以了，

/**
 * @param {string} S
 * @return {string[]}
 */
var letterCasePermutation = function(S) {
    let res = []
    let dfs = (t,str) => {
        if(t.length === S.length)
            return res.push(t)
        let ch = str[0]
        let nextStr = str.substr(1)
        // 當前位置為數字，只有一個分支
        if(!isNaN(Number(ch))){
            dfs(t+ch,nextStr)
        }else{
            //當前位置為字母，會產生兩個分支
            let tmp = ch.toUpperCase()
            if(tmp === ch) tmp = ch.toLowerCase()
            dfs(t+ch,nextStr)
            dfs(t+tmp,nextStr)
        }
    }
    dfs('',S)
    return res
};