[leetcode]

problem

code

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
    if (digits.length == 0) return [];
    
    const dial = {
        2: ['a', 'b', 'c'],
        3: ['d', 'e', 'f'],
        4: ['g', 'h', 'i'],
        5: ['j', 'k', 'l'],
        6: ['m', 'n', 'o'],
        7: ['p', 'q', 'r', 's'],
        8: ['t', 'u', 'v'],
        9: ['w', 'x', 'y', 'z']
    }
    
    var answer = [];
    recur(answer, '', dial, digits, 0);
    return answer;
    
};

var recur = (answer, str, dial, digits, i) => {
    if (i == digits.length) {
        answer.push(str);
        return;
    }
    
    for (const c of dial[digits[i]]) {
        recur(answer, str + c, dial, digits, i + 1);
    }
}

Time: O(4^N), N is the number of digits, 4 is the maximum number of dial characters
Space: O(N), N without ouput array, 4^N with the output array