Simple backtracking javascript solution


  • 0
    O

    This problem is just a classic "generate combinations" problem. The fact that we are given digits in the first place is a way to confuse candidates. Backtracking applies quite well here: for each digit, we want to generate all possible sequences with the letters associated to the digit, and carry on to the next digit.

    function letterCombinations(digits) {
        if (!digits.length) { return []; }
        
        const lettersMap   = [ ' ', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz' ];
        const combinations = [];
        backtrack('', 0);
        return combinations;
        
        function backtrack(string, i) {
            if (string.length === digits.length) {
                combinations.push(string);
                return;
            }
            
            const digit   = digits[i];
            const letters = lettersMap[digit];
            
            for (const letter of letters) {
                iterate(string + letter, i + 1);
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.