这个题的思想很重要，两种方法
第一种，回溯法
class Solution
{
public:
int sz;
vector<string> letterCasePermutation(string S)
{
vector<string> res;
sz=S.size();
backtrack(S,,res);
return res;
} void backtrack(string &s,int i,vector<string> &res)
{
if(i==sz)
{
res.push_back(s);
return ;
}
backtrack(s,i+,res);
if(isalpha(s[i]))
{
s[i]^=(<<);
backtrack(s,i+,res);
}
}
};
这个方法是先扫到末尾，再往回走，往回时遇到一个字母，改变其大小写，然后再把这个序列扫到末尾，改变之后的字母大小写。往回扫到第一个字符时，结束运行，输出结果。
第二种，顺序法
class Solution
{
public:
int sz;
vector<string> letterCasePermutation(string S)
{
vector<string> res;
sz=S.size();
letterCasePermutation(S,,res);
return res;
} void letterCasePermutation(string &s,int idx,vector<string> &res)
{
res.push_back(s);
for(int i=idx;i<sz;i++)
{
char temp=s[i];
if(isalpha(s[i]))
{
s[i]^=(<<);
letterCasePermutation(s,i+,res);
}
s[i]=temp;
}
}
};
这个方法和回溯法有点类似，只是这个是从头扫到尾，扫到第一个字符，改变大小写，然后递归，扫之后的字符。递归完成后，说明改变这个字符之后，右边字符序列改变的组合已经完成了。然后把字符变回去，继续向右扫，直到扫描完成。