Letter Case Permutation Problem
Description
LeetCode Problem 784.
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. You can return the outputin any order.
Example 1:
1
2
Input: s = "a1b2"
Output: ["a1b2","a1B2","A1b2","A1B2"]
Example 2:
1
2
Input: s = "3z4"
Output: ["3z4","3Z4"]
Example 3:
1
2
Input: s = "12345"
Output: ["12345"]
Example 4:
1
2
Input: s = "0"
Output: ["0"]
Constraints:
- s will be a string with length between 1 and 12.
- s will consist only of letters or digits.
Sample C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
void backtrack(string &s, int i, vector<string> &res) {
if (i == s.size()) {
res.push_back(s);
return;
}
backtrack(s, i + 1, res);
if (isalpha(s[i])) {
// toggle case
s[i] ^= (1 << 5);
backtrack(s, i + 1, res);
}
}
public:
vector<string> letterCasePermutation(string S) {
vector<string> res;
backtrack(S, 0, res);
return res;
}
};