LeetCode Solutions
784. Letter Case Permutation
Time: $O(2^n)$ Space: $O(2^n)$
class Solution {
public:
vector<string> letterCasePermutation(string S) {
vector<string> ans;
dfs(S, 0, ans);
return ans;
}
private:
void dfs(string& S, int i, vector<string>& ans) {
if (i == S.length()) {
ans.push_back(S);
return;
}
if (isdigit(S[i])) {
dfs(S, i + 1, ans);
return;
}
S[i] = tolower(S[i]);
dfs(S, i + 1, ans);
S[i] = toupper(S[i]);
dfs(S, i + 1, ans);
}
};
class Solution {
public List<String> letterCasePermutation(String S) {
List<String> ans = new ArrayList<>();
dfs(new StringBuilder(S), 0, ans);
return ans;
}
private void dfs(StringBuilder sb, int i, List<String> ans) {
if (i == sb.length()) {
ans.add(sb.toString());
return;
}
if (Character.isDigit(sb.charAt(i))) {
dfs(sb, i + 1, ans);
return;
}
sb.setCharAt(i, Character.toLowerCase(sb.charAt(i)));
dfs(sb, i + 1, ans);
sb.setCharAt(i, Character.toUpperCase(sb.charAt(i)));
dfs(sb, i + 1, ans);
}
}