[leetcode] Letter Case Permutation

problem

code

javascript

/**
 * @param {string} S
 * @return {string[]}
 */
var letterCasePermutation = function(S) {
    const onlyNumReg = /^[0-9]+$/;
    if(onlyNumReg.test(S)) 
      return [S];
  
    return [...S].reduce((acc, c) => {
        if(onlyNumReg.test(c)) 
            return acc.map(str => str + c);
        
        const temp = [];
        acc.forEach(str => {
            temp.push(str + c.toLocaleLowerCase());
            temp.push(str + c.toLocaleUpperCase());
        });
        return temp;
    }, [""]);
};

Time: O(N + 2^N), reduce N, concat string + each character 2^N
Space: O(2^N), if S consists of only alphabets an answer list contains 2^N

explain

S = 'a1b4';
list = [];

1 'a' ['a', 'A']
2. '1' ['a1', 'A1']
3. 'b' ['a1b', 'a1B', 'A1b', 'A1B']
4. '4' ['a1b4', 'a1B4', 'A1b4', 'A1B4']

java

class Solution {
    public List<String> letterCasePermutation(String S) {
        List<String> ans = new ArrayList<>();
        if(S.length() == 0){
            return ans;
        }
        helper(S.toCharArray(), ans, 0);
        return ans;
    }

    private void helper(char[] str, List<String> ans, int index){
        if(index == str.length){
            ans.add(new String(str));
            return ;
        }

        if(Character.isDigit(str[index])){
            helper(str, ans, index+1);
            return ;
        } else{
            str[index] = Character.toLowerCase(str[index]);
            helper(str, ans, index+1);


            str[index] = Character.toUpperCase(str[index]);
            helper(str, ans, index+1);
        }
    }
}

java ref: leetcode