Combinations of Phone Number#

Given a string containing only digits 2-9, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example#

Solution#

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
    var n = digits.length;
    var target = [];
    if(!n) return target;
    var map = { 
        "2": "abc", 
        "3": "def", 
        "4": "ghi", 
        "5": "jkl", 
        "6": "mno", 
        "7": "pqrs", 
        "8": "tuv", 
        "9": "wxyz" 
    };
    var dfs = function(i, tmp){
        if(i === n) {
            target.push(tmp);
            return void 0;
        }
        var unit = map[digits[i]];
        Array.prototype.forEach.call(unit, v => dfs(i+1,`${tmp}${v}`));
    }
    dfs(0, "");
    return target;
};

Idea#

Backtracking, for a given input, it can form a tree and then use backtracking to traverse the tree to obtain all letter combinations. First, define n as the length of the input key, then define the target array. If the length of the key is 0, return an empty array directly. Define a map as the mapping between the key and letters, then define a dfs to recursively call, if the current recursion position i is equal to the input key length, put the concatenated string into the target array and finish the recursion. Then get all characters of the key, then traverse the string and append it to the existing string and then recursively pass the current tree depth and the concatenated string. Then start the recursion, after the recursion is completed, return the target array.

Daily Topic#

Reference#