题意: 给定一个字符串, 输出所有字符大小写都可以组成的字符串.
如: “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
GD Star Rating
loading...
本文一共 133 个汉字, 你数一下对不对.loading...
上一篇: 编程练习题: 找出N叉树的深度
下一篇: C++编程练习题: 找出数组中所有重复的元素
扫描二维码,分享本文到微信朋友圈