Letter Combinations of a Phone Number

Problem

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

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 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = ""
Output: []

Example 3:

Input: digits = "2"
Output: ["a","b","c"]

Constraints:

0 <= digits.length <= 4
digits[i] is a digit in the range ['2', '9'].

Solution

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

var backtrack = function(res, index, path, digits, map) {
    if (index === digits.length) {
        if (path) {
            res.push(path);
        }
    } else {
        const d = digits[index];
        for (const c of map[d - 2]) {
            backtrack(res, index + 1, path + c, digits, map);
        }
    }
};

We will implement a backtracking (DFS) solution. We recursively build up all possible letter combinations based on the order of digits. Note that a BFS solution is also easily attainable, and would provide better space complexity.

Problem​

Solution​

Problem

Solution