Day134 | 灵神 | 回溯算法 | 子集型 字母大小写全排列

784.字母大小写全排列

784. 字母大小写全排列 - 力扣（LeetCode）

思路：

这道题用选或不选的思路来解答。选或不选说的不是选或不选s字符串中的某个字符，而是选或不选改变s字符串中字符的大小写

如果是数字的话就不用说了，我们直接输入到path就行

如果是字母的话，那就有两种情况

1.选择不改变其大小写直接输入到path，这种就是原来什么样子现在还什么样

2.选择改变其大小写直接输入到path，这种就是改变了大小写以后放进去的

需要注意的点：对于同一个结点有多个状态，比如这道题，在选择字母a之后，字母a还有两个状态一个改变大小写一个不改变。如果是这种情况的话就要把两个状态都给列出来，即小写a输入path后递归一遍，大写a输入path后再递归一遍

完整代码：

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
class Solution {
public:
    vector<string> res;
    void backtracking(string &s,string path,int i)
    {
        if(path.size()==s.size())
        {
            res.push_back(path);
            return ;
        }
        //是数字的话直接选
        if(s[i]>='0'&&s[i]<='9')
        {
            path.push_back(s[i]);
            backtracking(s,path,i+1);
            path.pop_back();
        }
        //不是数字的话要分大小写的情况
        else
        {
            //选择不改变原来字符
            path.push_back(s[i]);
            backtracking(s,path,i+1);
            path.pop_back();
            //选择改变原来字符
            s[i]^=32;
            path.push_back(s[i]);
            backtracking(s,path,i+1);
            s[i]^=32;
            path.pop_back();
        }
    }
    vector<string> letterCasePermutation(string s) {
        string path;
        backtracking(s,path,0);
        return res;
    }
};

转换大小写的简便写法，大转小小转大一次完成（记住）

^=32 是一个位运算操作，使用按位异或（XOR）来切换字母的大小写：

  1. ASCII码基础：

    • 在ASCII编码中，大小写字母正好相差32
    • 大写字母A-Z：65-90
    • 小写字母a-z：97-122
    • 二进制表示：大小写字母的第6位不同（从0开始计数）

  2. 按位异或（XOR）原理：

    • XOR运算规则：相同为0，不同为1
    • a ^= 32 等价于 a = a ^ 32
    • 32的二进制：00100000（只影响第5位）

  3. 实际效果：

    1
    2
    3
    4
    5
    'a' (97) 的二进制: 01100001
    XOR 32(00100000) → 01000001 = 65 → 'A'

    'A' (65) 的二进制: 01000001
    XOR 32(00100000) → 01100001 = 97 → 'a'