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);
  }
}