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

写在前面

难度：简单回溯法 + 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; } 参考文章 【回顾&小结】回溯法leetcode 784. 字母大小写全排列（c++位运算）利用ASCII码与位运算异或进行大小写转换（ASCII码两组大小写字母间为何隔着6个字符）CodeBlocks17.12下载安装及调试时看字符数组内的变量