784. Letter Case Permutation

784. Letter Case Permutation

Solution

• time complexity O(2^N) N equals to the number of characters

class Solution {
  public List<String> letterCasePermutation(String S) {
    List<String> res = new ArrayList<>();
    permutate(S, "", 0, res);

    return res;
  }

  private void permutate(String s, String str, int idx, List<String> res){
    if(idx == s.length()){
      res.add(str);
      return;
    }
    char c = s.charAt(idx);
    if(Character.isLetter(c)){
      permutate(s, str + Character.toLowerCase(c), idx + 1, res);
      permutate(s, str + Character.toUpperCase(c), idx + 1, res);
    }else{ // is digit
      str += c;
      permutate(s, str, idx + 1, res);
    }
  }
}