【回溯算法】leetcode 784. 字母大小写全排列

784. 字母大小写全排列

题目描述

给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。

返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。

示例1：

输入： s = “a1b2”
输出： [“a1b2”, “a1B2”, “A1b2”, “A1B2”]

示例2：

输入： s = “3z4”
输出： [“3z4”,“3Z4”]

提示

• $1<=s.length<=12$
• $s由小写英文字母、大写英文字母和数字组成$

方法：回溯算法

解题思路

既然数字涉及不到分支，遇到它的时候，不妨继续往后搜，因此对于一个数字只需搜 1 次。但对于单个字母来说，我们需要搜 2 次：小写的时候搜一次，大写的时候再搜一次。

再具体一点：遇到数字直接 index + 1 继续递归，遇到字母则连续递归 2 次，即当字母为小写的时候递归一次 (index + 1)，然后回溯时将字母转为大写，又去递归一次。

什么时候保存搜索的结果？当然是递归的尽头，一次完整的搜索要等到递归到满足终止条件才会结束。递归的尽头即搜索完整个字符串，我们要找的结果就是上图中所有的叶子节点。

代码

class Solution {
public:
    vector<string> result;
    void dfs(int startIndex, string s) {
        if(startIndex == s.size()) {
            result.push_back(s);
            return;
        }
        if(isalpha(s[startIndex])) {
            dfs(startIndex + 1, s);
            s[startIndex] ^= 32;
            dfs(startIndex + 1, s);
        } else {
            dfs(startIndex + 1, s);
        }
    }
    vector<string> letterCasePermutation(string s) {
        dfs(0, s);
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

复杂度分析

• 时间复杂度：$O(n\times 2^n)$。
• 空间复杂度：$O(n\times 2^n)$。