Leetcode刷题详解——字母大小写全排列

1. 题目链接：784. 字母大小写全排列

2. 题目描述：

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

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

示例 1：

输入：s = "a1b2"
输出：["a1b2", "a1B2", "A1b2", "A1B2"]
1
2

示例 2:

输入: s = "3z4"
输出: ["3z4","3Z4"]
1
2

提示:

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

3. 算法（递归）：

3.1 算法思路：

只需要对英文字母进行处理，处理每个元素时存在三种情况：

1. 不进行处理
2. 若当前字母是英文字母并且是大写，将其修改为小写
3. 若当前字母是英文字母并且是小写，将其修改为大写

3.2 递归流程：

1. 递归结束条件：当前需要处理的元素下标越界，表示处理完毕，记录当前状态并返回
2. 对当前元素不进行任何处理，直接递归下一位元素
3. 判断当前元素是否为小写字母。若是将其修改为大写字母并递归下一个元素，递归结束时撤销修改操作
4. 判断当前元素是否为大写字母，若是将其修改为小写字母并递归下一个元素，递归结束时撤销修改操作

3.3 C++算法代码：

class Solution {
    string path; // 用于存储当前路径的字符串
    vector ret; // 用于存储所有可能的排列结果

public:
    // 主函数，接收输入字符串s，返回所有可能的排列结果
    vector letterCasePermutation(string s) {
        dfs(s, 0); // 调用深度优先搜索函数进行递归遍历
        return ret; // 返回所有可能的排列结果
    }

    // 深度优先搜索函数，接收输入字符串s和当前位置pos
    void dfs(string& s, int pos) {
        // 如果当前位置等于字符串长度，说明已经遍历完整个字符串
        if (pos == s.size()) {
            ret.push_back(path); // 将当前路径添加到结果列表中
            return; // 结束当前递归分支
        }

        char ch = s[pos]; // 获取当前位置的字符
        path.push_back(ch); // 将当前字符添加到路径中
        dfs(s, pos + 1); // 继续递归遍历下一个位置
        path.pop_back(); // 回溯，移除路径中的最后一个字符

        // 如果当前字符不是数字，则尝试将其大小写互换并继续递归遍历
        if (ch < '0' || ch > '9') {
            char tmp = change(ch); // 调用change函数将字符大小写互换
            path.push_back(tmp); // 将大小写互换后的字符添加到路径中
            dfs(s, pos + 1); // 继续递归遍历下一个位置
            path.pop_back(); // 回溯，移除路径中的最后一个字符
        }
    }

    // 辅助函数，用于将小写字母转换为大写字母，大写字母转换为小写字母
    char change(char ch) {
        if (ch >= 'a' && ch <= 'z')
            ch -= 32; // 如果是小写字母，将其转换为大写字母
        else
            ch += 32; // 如果是大写字母，将其转换为小写字母
        return ch; // 返回转换后的字符
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43