leetcode-784. 字母大小写全排列刷题笔记（c++）

比眉伴天荒 2023-02-21 12:52 8阅读 0赞

#### 写在前面 ####

*  难度：简单
 *  回溯法 + `vector<string>`数组
 *  新笔记
    
     *  回溯法主要用于解决组合问题，要求一般是最后的组合不能有重复。
     *  是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。
        
         *  待深入学习、研究

// 传统方法进行大小写转换
    if(ch >= 'a' && ch <= 'z') ch -= 32;
    if(ch >= 'A' && ch <= 'Z') ch += 32;
    
    // 字母大小写转换: XOR (32 or (1 << 5))
    // 改良后转换方式
    if(ch >= 'a' && ch <= 'z' || ch >= 'A' && ch <= 'Z') ch ^= ' ';
    
    // 因为空格的ASCII码即为32！！！！！！

#### 题目详情 ####

给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。
    
    示例:
    输入: S = "a1b2"
    输出: ["a1b2", "a1B2", "A1b2", "A1B2"]
    
    输入: S = "3z4"
    输出: ["3z4", "3Z4"]
    
    输入: S = "12345"
    输出: ["12345"]
    注意：
    
    S 的长度不超过12。
    S 仅由数字和字母组成。

#### ac代码 ####

*  方法1：`回溯法`

class Solution
    {
        
        void backtrack(string &s, int i, vector<string> &res)
        {
        
            if (i == s.size())
            {
        
                res.push_back(s);
                return;
            }
            backtrack(s, i + 1, res);
            if (isalpha(s[i]))
            {
        
                s[i] ^= 32;
                backtrack(s, i + 1, res);
            }
        }
    public:
        vector<string> letterCasePermutation(string S)
        {
        
            vector<string> res;
            backtrack(S, 0, res);
            return res;
        }
    };

*  方法2：`dfs + 回溯`

class Solution
    {
        
    public:
        vector<string> ans;
        vector<string> letterCasePermutation(string S)
        {
        
            dfs(S,0);
            return ans;
        }
        void dfs(string S,int n)
        {
        
            if(n==S.size())
            {
        
                ans.push_back(S);
                return;
            }
            dfs(S,n+1);
            if(S[n] >= 65)
            {
        
                S[n] ^= 32;
                dfs(S,n+1);
            }
        }
    };

*  测试代码
    
     *  算法思想值得学习、思考

#include <iostream>
    #include <vector>
    using namespace std;
    
    void backtrack(string &s, int i, vector<string> &res)
    {
        
        cout << s << " " << i << " " << res.size() << endl;
        if (i == s.size())
        {
        
            res.push_back(s);
            return;
        }
        backtrack(s, i + 1, res);
        if (isalpha(s[i]))
        {
        
            // s[i] ^= 32;
            s[i] ^= (1 << 5);
            backtrack(s, i + 1, res);
            cout << s << "-" << i << "-" << res.size() << endl;
        }
    }
    vector<string> letterCasePermutation(string S)
    {
        
        vector<string> res;
        backtrack(S, 0, res);
        return res;
    }
    int main()
    {
        
        string S = "a1b2";
        vector<string> ans = letterCasePermutation(S);
        for(auto ss : ans)
            cout << ss << " " << endl;
        return 0;
    }

*  参考文章
    
     *  [【回顾&小结】回溯法][Link 1]
     *  [leetcode 784. 字母大小写全排列（c++位运算）][leetcode 784. _c]
     *  [利用ASCII码与位运算异或进行大小写转换（ASCII码两组大小写字母间为何隔着6个字符）][ASCII_ASCII_6]
     *  [CodeBlocks17.12下载安装及调试时看字符数组内的变量][CodeBlocks17.12]

[Link 1]: https://segmentfault.com/a/1190000012218890
[leetcode 784. _c]: https://blog.csdn.net/qtmatt/article/details/97044057
[ASCII_ASCII_6]: https://blog.csdn.net/weixin_44129784/article/details/104100539
[CodeBlocks17.12]: https://blog.csdn.net/hy1255564202/article/details/102841488