类似于二叉树的前序遍历,左分支代表不转换字母的大小写,右分支代表转换字母的大小写,如果遇到数字就跳过,继续遍历下一个位置,循环的终止条件是扫描到最后一个元素的下一个位置。(如果扫描到最后一个元素就停止的话,那么最后一个元素可能还没有进行大小写转换,所以我们要扫描到最后一个元素的下一个位置,以确保字符串中所有的字母都大小写转换过)
class Solution {
public:
vector<string> res;
void dfs(string &s, int u)
{
// 遇到数字就跳过,继续扫描下一个位置
while (u < s.size() && isdigit(s[u])) u ++;
if (u == s.size())
{
res.push_back(s);
return ;
}
// 遇到字母时,产生两个分支
// 不进行大小写转换
dfs(s, u + 1);
// 进行大小写转换
s[u] ^= 32;
dfs(s, u + 1);
s[u] ^= 32; // 恢复到转换之前的状态
}
vector<string> letterCasePermutation(string s) {
dfs(s, 0);
return res;
}
};