LeetCode784. Letter Case Permutation 记录调试经验cout 中使用多个空格输出数值题目说明思路子集树排序树调试记录回溯法参考题目说明Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create.Examples: Input: S a1b2 Output: [a1b2, a1B2, A1b2, A1B2] Input: S 3z4 Output: [3z4, 3Z4] Input: S 12345 Output: [12345]Note:S will be a string with length between 1 and 12.S will consist only of letters or digits.思路这个题使用回溯法(递归进行DFS)是很合适的这里总结几点子集树这种类型的回溯法可以归纳成寻找满足某种性质的解时可以用一棵完全二叉树表示解空间当所给的问题是从 n 个元素中找出满足某种性质的子集时相应的解空间树称为 子集树这类子集树通常有个2 n 2^{n}2n叶节点其节点总数为2 n 1 − 1 2^{n 1} - 12n1−1遍历子集树的任何算法均需要Ω ( 2 n ) Ω(2^{n})Ω(2n)的计算时间给出该种解法的模板void backtrack(int t) { if (t n) Output(x);//tn的条件谨慎选择后面的操作可能使它超出n的限制 else for (int i 0; i 1; i) { // 0 或 1 选或不选 x[t] i; if (Constraint(t) Bound(t)) backtrack(t 1); // Constraint() 约束函数 Bound() 限界函数 //Bound()函数尤其重要否则可能造成堆栈溢出 //如果有需要要在回溯执行后恢复现场 } }排序树回溯法的另一种类型排序树当所给的问题是确定 n 个元素满足某种性质的排列时相应的解空间树称为 排列树 通常有个n ! n!n!叶节点遍历子集树的任何算法均需要 Ω(n!) 的计算时间void backtrack(int t) { if (t n) Output(x); else for (int i t; i n; i) { swap(x[t],x[i]); if (Constraint(t) Bound(t)) backtrack(t 1); swap(x[t],x[i]); //恢复现场 } }上代码class Solution { public: vectorstring letterCasePermutation(string S) { vectorstring res; if(S.length() 0)return res; get(0, S, res); return res; } void get(int index, string S, vectorstring res){ if(index S.length()){ res.push_back(S); return; } while(index S.length() S[index] 9 S[index] 0)index ; get(index 1, S, res); if (index S.length() (S[index] 9 || S[index] 0)) { S[index] (S[index] a S[index] z) ? (A - a) : (a - A); get(index 1, S, res); S[index] (S[index] a S[index] z) ? (A - a) : (a - A); } return; } };调试记录在下面这个主函数中在输出时使用cout ’ 输出就变成了8224如果把两个空格变成一个才是空格输出int main() { string s; Solution S; while (getline(cin,s)) { vectorstring res S.letterCasePermutation(s); //下面这一行输出中的空格问题 for (int i 0; i res.size(); i )cout res[i] ; cout endl; } return 0; }特此记录回溯法参考https://blog.csdn.net/machinerandy/article/details/81915841