题目描述

给定一个字符串S，我们可以将其中的大写字母换成小写字母，或将小写字母换成大写字母，从而得到一个新的字符串。

请返回所有可能得到的字符串。

注意：

• S的长度范围是[1, 12]；
• S中只包含字母和数字；

样例1

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

样例2

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

样例3

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

算法

(DFS) $O(n \times 2^n)$

深度优先搜索。从左到右一位一位枚举：

• 如果遇到数字，则直接跳过当前位，枚举下一位；
• 如果遇到字母，则分别将当前位设成小写字母和大写字母，然后递归到下一位；

小技巧：可以用位运算改变当前字母的大小写，从而简化代码：将一个字母异或32，即可改变这个字母的大小写。比如：

• 'a' ^ 32 = 'A';
• 'B' ^ 32 = 'b';

时间复杂度分析：最坏情况下，所有字符都是字母，则每个字符都有两种选择，一共会得到 $2^n$ 个字符串，最后将每个字符串记录在答案中还需要 $O(n)$ 的计算量，所以总时间复杂度是 $O(n \times 2^n)$。

C++ 代码

class Solution {
public:

    vector<string> ans;

    vector<string> letterCasePermutation(string S) {
        dfs(S, 0);
        return ans;
    }

    void dfs(string &S, int u)
    {
        if (u == S.size())
        {
            ans.push_back(S);
            return;
        }
        dfs(S, u + 1);
        if (S[u] >= 'A')
        {
            S[u] ^= 32;
            dfs(S, u + 1);
        }
    }
};