題目網址：https://leetcode.cn/problems/letter-case-permutation/

題意：給一 string s, 將 s 中的每個字母轉變大小寫, 可得到新的 string。求所有可能的 string, 可以按順序任意排列。

Solution：

想法：利用 DFS + Backtracking

  • 若 s[i] 為數字, 則 s[i] 不變繼續往後走
  • 若 s[i] 為字母, 則有兩種情況：

    • s[i] 不變繼續往後走

    • s[i] 轉變大小寫後, 繼續往後走

class Solution {
public:
    vector<string> letterCasePermutation(string s) {
        dfs(s, 0, s.size());
        return res;
    }

private:
    vector<string> res;

    void dfs(string& s, const int i, const int n){
        if (i == n) {
            res.emplace_back(s);
            return;
        }

        // 不論是字母還是數字, 都先自己不變, 並往下一個走
        dfs(s, i + 1, n);

        if (isalpha(s[i])) {
            // 因為 'a' - 'A' = 32 = 2^5
            // 在 s[i] 為字母的條件下, 對右邊數來第5個 bit 跟 1 做 XOR
            // 因為 XOR: (0, 1) = 1, (1, 1) = 0
            s[i] ^= (1 << 5); // 等同於 s[i] 根據大小寫 +/- 32
            dfs(s, i + 1, n);
            s[i] ^= (1 << 5); // XOR 做兩次相同運算 = 還原
        }
    }
};
  • time：$O(n \cdot 2^n)$
    • 最多 $2^n$ 種狀態（n 個都字母）
    • 建每一種狀態的需 $O(n)$
  • space：$O(n \cdot 2^n)$ ➔ $O(n) + O(n \cdot 2^n)$
    • $O(n)$ : dfs() 遞迴最大深度
    • $O(n \cdot 2^n)$ : 最多 $2^n$ 種狀態（n 個都字母）, 每種狀態的 string 長度都為 n