DFS Recursion
Time complexity = O(n * 2^l): l is # of letters, n is the # of all characters (depth of recursion)
Space complexity = O(n) + O(n * 2^l): stack + sol
class Solution {
public List<String> letterCasePermutation(String S) {
List<String> res = new ArrayList<>();
if (S == null || S.length() == 0) {
return res;
}
StringBuilder sb = new StringBuilder();
char[] sArray = S.toCharArray();
permutationHelper(sb, 0, sArray, res);
return res;
}
private void permutationHelper(StringBuilder sb, int index, char[] sArray, List<String> res) {
if (sb.length() == sArray.length) {
res.add(sb.toString());
return;
}
char cur = sArray[index];
if (Character.isLetter(cur)) {
permutationHelper(sb.append(Character.toLowerCase(cur)), index + 1, sArray, res);
sb.deleteCharAt(sb.length() - 1);
permutationHelper(sb.append(Character.toUpperCase(cur)), index + 1, sArray, res);
sb.deleteCharAt(sb.length() - 1);
} else {
permutationHelper(sb.append(cur), index + 1, sArray, res);
sb.deleteCharAt(sb.length() - 1);
}
}
}