[LeetCode] Problem 784 - Letter Case Permutation

Posted on | In ,

Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create.

Example

No.1

Input: S = “a1b2”

Output: [“a1b2”, “a1B2”, “A1b2”, “A1B2”]

No.2

Input: S = “3z4”

Output: [“3z4”, “3Z4”]

No.3

Input: S = “12345”

Output: [“12345”]

Note

  • S will be a string with length between 1 and 12.
  • S will consist only of letters or digits.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public List<String> letterCasePermutation(String S) {
    List<String> result = new ArrayList<>();
    dfs(result, S.toCharArray(), 0);
    return result;
}

private void dfs(List<String> result, char[] str, int idx) {
    if (idx == str.length) {
        result.add(String.valueOf(str));
        return;
    }

    dfs(result, str, idx + 1);
    char ch = str[idx];

    if (Character.isLetter(ch)) {
        str[idx] = (char) (ch ^ (1 << 5));
        dfs(result, str, idx + 1);
        str[idx] = ch;
    }
}