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:
S will be a string with length between 1 and 12.S will consist only of letters or digits.
Approach #1: BFS. [C++].
class Solution {
public:
vector<string> letterCasePermutation(string S) {
set<string> memo;
memo.insert(S);
helper(S, 0, memo);
vector<string> ans(memo.begin(), memo.end());
return ans;
}
private:
void helper(string S, int idx, set<string>& memo) {
if (idx >= S.length()) return;
vector<string> temp(memo.begin(), memo.end());
//cout << idx << endl;
for (string s : temp) {
if (isalpha(s[idx])) {
char c;
if (isupper(s[idx])) c = tolower(s[idx]);
else c = toupper(s[idx]);
//cout << c << endl;
string temp = s;
temp[idx] = c;
if (!memo.count(temp)) memo.insert(temp);
//helper(S, idx+1, memo);
}
}
helper(S, idx+1, memo);
}
};
原文：https://www.cnblogs.com/ruruozhenhao/p/10356812.html