784. Letter Case Permutation

,

Bit

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
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    private static final int DIFF = 'a' - 'A';

    public List<String> letterCasePermutation(String s) {
        List<String> resultList = new ArrayList<>();

        for (int mask = 0; mask < 1 << s.length(); mask++) {
            char[] chars = s.toCharArray();

            boolean duplicate = false;
            for (int i = 0; i < chars.length; i++) {
                // 注意数字不能翻转
                if (Character.isDigit(chars[i]) && ((mask >> i) & 1) == 1) {
                    duplicate = true;
                    break;
                }
                
                if (((mask >> i) & 1)== 1) {
                    chars[i] = flip(chars[i]);
                }
            }

            if (!duplicate) {
                resultList.add(new String(chars));
            }
        }

        return resultList;
    }

    private char flip(char c) {
        if (c >= 'a') {
            return (char) (c - DIFF);
        } else {
            return (char) (c + DIFF);
        }
    }
}

Bit

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
26
27
28
29
30
class Solution {
    public List<String> letterCasePermutation(String s) {
        List<String> resultList = new ArrayList<>();
        int letterCount = 0;
        for (int i = 0; i < s.length(); i++) {
            if (!Character.isDigit(s.charAt(i))) {
                letterCount++;
            }
        }

        for (int mask = 0; mask < 1 << letterCount; mask++) {
            char[] chars = s.toCharArray();
            int letterOffset = 0;
            for (int i = 0; i < chars.length; i++) {
                if (!Character.isDigit(chars[i])) {
                    if (((mask >> letterOffset) & 1) == 0) { // 注意此时要移动 letterOffset
                        chars[i] = Character.toLowerCase(chars[i]);
                    } else {
                        chars[i] = Character.toUpperCase(chars[i]);
                    }
                    letterOffset++;
                }
            }

            resultList.add(new String(chars));
        }

        return resultList;
    }
}

DFS

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
26
27
28
29
30
class Solution {
    public List<String> letterCasePermutation(String s) {
        List<String> resultList = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        dfs(resultList, sb, s, 0);
        return resultList;
    }

    private void dfs(List<String> resultList, StringBuilder sb, String s, int i) {
        if (i == s.length()) {
            resultList.add(sb.toString());
            return;
        }

        char c = s.charAt(i);
        if (Character.isDigit(c)) {
            sb.append(c);
            dfs(resultList, sb, s, i + 1);
            sb.deleteCharAt(sb.length() - 1);
        } else {
            sb.append(Character.toLowerCase(c));
            dfs(resultList, sb, s, i + 1);
            sb.deleteCharAt(sb.length() - 1);
            
            sb.append(Character.toUpperCase(c));
            dfs(resultList, sb, s, i + 1);
            sb.deleteCharAt(sb.length() - 1);
        } 
    }
}

DFS

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

    private void dfs(List<String> resultList,char[] chars, int i) {
        if (i == chars.length) {
            resultList.add(new String(chars));
            return;
        }

        dfs(resultList, chars, i + 1); // not flip
        if (Character.isLetter(chars[i])) {
            // flip
            chars[i] ^= ' ';
            dfs(resultList, chars, i + 1);
        }
    }
}

References

784. Letter Case Permutation