学编程
题意: 给定一个字符串, 输出所有字符大小写都可以组成的字符串.
如: “ab1” 能成生 [“ab1”, “Ab1”, “aB1”, “AB1”]
DFS 深度优先 – 递归
我们可以从字符串的开头递归的把当前字符给添加到最终的字符串中, 当当前字符是字母的时候, 就有两种可能了. 当到达字符串尾部的时候我们把当前字符串添加到结果数组中即可.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | class Solution { public: vector<string> letterCasePermutation(string S) { search("", S, 0, S.length() - 1); return r; } private: vector<string> r; void search(string cur, string S, int i, int j) { if (i > j) { r.push_back(cur); return ; } auto ch1 = string(1, std::toupper(S[i])); // 把字符转成串 search(cur + ch1, S, i + 1, j); auto ch2 = string(1, std::tolower(S[i])); if (ch2 != ch1) { // 如果是字母 search(cur + ch2, S, i + 1, j); } } }; |
class Solution {
public:
vector<string> letterCasePermutation(string S) {
search("", S, 0, S.length() - 1);
return r;
}
private:
vector<string> r;
void search(string cur, string S, int i, int j) {
if (i > j) {
r.push_back(cur);
return ;
}
auto ch1 = string(1, std::toupper(S[i])); // 把字符转成串
search(cur + ch1, S, i + 1, j);
auto ch2 = string(1, std::tolower(S[i]));
if (ch2 != ch1) { // 如果是字母
search(cur + ch2, S, i + 1, j);
}
}
};英文: C++ Coding Exercise – Find Letter Case Permutation with DFS
强烈推荐
- 英国代购-畅购英伦
- TopCashBack 返现 (英国购物必备, 积少成多, 我2年来一共得了3000多英镑)
- Quidco 返现 (也是很不错的英国返现网站, 返现率高)
- 注册就送10美元, 免费使用2个月的 DigitalOcean 云主机(性价比超高, 每月只需5美元)
- 注册就送10美元, 免费使用4个月的 Vultr 云主机(性价比超高, 每月只需2.5美元)
- 注册就送10美元, 免费使用2个月的 阿里 云主机(性价比超高, 每月只需4.5美元)
- 注册就送20美元, 免费使用4个月的 Linode 云主机(性价比超高, 每月只需5美元) (折扣码: PodCastInit2022)
- PlusNet 英国光纤(超快, 超划算! 用户名 doctorlai)
- 刷了美国运通信用卡一年得到的积分 换了 485英镑
- 注册就送50英镑 – 英国最便宜最划算的电气提供商
- 能把比特币莱特币变现的银行卡! 不需要手续费就可以把虚拟货币法币兑换
微信公众号: 小赖子的英国生活和资讯 JustYYUK