企业官网建设流程全解析

题目说明

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:

1. S will be a string with length between 1 and 12.
2. S will consist only of letters or digits.

思路

这个题使用回溯法(递归进行DFS)是很合适的，这里总结几点

子集树

这种类型的回溯法可以归纳成寻找满足某种性质的解时，可以用一棵完全二叉树表示解空间
当所给的问题是从 n 个元素中找出满足某种性质的子集时，相应的解空间树称为 子集树，这类子集树通常有个2 n 2^{n}2n叶节点，其节点总数为2 n + 1 − 1 2^{n + 1} - 12n+1−1，遍历子集树的任何算法均需要Ω ( 2 n ) Ω(2^{n})Ω(2n)的计算时间
给出该种解法的模板

void backtrack(int t) { if (t > n) Output(x);//t>n的条件谨慎选择，后面的操作可能使它超出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: vector<string> letterCasePermutation(string S) { vector<string> res; if(S.length() == 0)return res; get(0, S, res); return res; } void get(int index, string &S, vector<string> &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)) { vector<string> 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