784. Letter Case Permutation

 一刷 06/2022

Version #1 DFS backtracking

Time O(N*2^N) - the worst case each character could have a fan out factor of 2, and we need extra O(N) time to create the result string

Space O(N) - depth of the stack

Runtime: 3 ms, faster than 87.39% of Java online submissions for Letter Case Permutation.

Memory Usage: 54.1 MB, less than 44.99% of Java online submissions for Letter Case Permutation.

class Solution {

    public List<String> letterCasePermutation(String s) {

        char[] chars = s.toCharArray();

        // dfs

        List<String> result = new ArrayList<>();

        dfs(chars, 0, result);

        return result;

    }

    

    private void dfs(char[] chars, int index, List<String> result) {

        if (index == chars.length) {

            result.add(new String(chars));

            return;

        }

        if (Character.isDigit(chars[index])) {

            dfs(chars, index + 1, result);

            return;

        }

        char c = chars[index];

        chars[index] = Character.toLowerCase(c);

        dfs(chars, index + 1, result);

        chars[index] = Character.toUpperCase(c);

        dfs(chars, index + 1, result);

        chars[index] = c;

    }

}

Version #2 Bit mask

Time O(N*2^N)

Space O(N) for string builder

class Solution {

    public List<String> letterCasePermutation(String s) {

        // Count how many letters are there in the string

        // we can use 0 to represent lower case and 1 to represent upper case

        // Then the result could be represent uniquely by bit mask [0 ~ 1 << N)

        int N = 0;

        for (int i = 0; i < s.length(); i++) {

            if (Character.isLetter(s.charAt(i))) {

                N++;

            }

        }

        List<String> result = new ArrayList<>();

        for (int bits = 0; bits < (1 << N); bits++) {

            StringBuilder sb = new StringBuilder();

            int b = 0;

            for (int i = 0; i < s.length(); i++) {

                char c = s.charAt(i);

                if (Character.isDigit(c)) {

                    sb.append(c);

                    continue;

                }

                if (((bits >> b) & 1) == 1) {

                    sb.append(Character.toUpperCase(c));

                } else {

                    sb.append(Character.toLowerCase(c));

                }

                b++;

            }

            result.add(sb.toString());

        }

        return result;

    }

}