Skip to content

784. Letter Case Permutation 👍

  • Time: $O(2^n)$
  • Space: $O(2^n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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);
  }
}