0017. Letter Combinations of a Phone Number.md

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.

Complexity can't possibly be below 4^n, since there are up to 4^n outputs for input of length n.

C++

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        unordered_map<char, string> obj = {
            {'2', "abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"}
        };

        if(!digits.size()) return {};

        vector<string> res;
        string path;

        function<void(int)> backtrack = [&](int start) {
            if(path.size() == digits.size()) {
                res.push_back(path);
                return;
            }

            string letters = obj[digits[start]];
            for(auto letter : letters) {
                path.push_back(letter);
                backtrack(start + 1);
                path.pop_back();
            }
        };

        backtrack(0);
        return res;
    }
};

JavaScript

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
    const map = {
        2: 'abc',
        3: 'def',
        4: 'ghi',
        5: 'jkl', 
        6: 'mno',
        7: 'pqrs',
        8: 'tuv',
        9: 'wxyz',
    }
    
    // we need this, otherwise cannot pass "" case,
    // where expected is [], we output [""]
    if(!digits.length) return [];
    const res = [];
    
    function dfs(s, i) {
        if(i === digits.length) {
            res.push(s);
            return;
        }
        // For example, digits is "23"
        // map[digits[i]] = map[digits[0]] = 'abc'
        // letter traverse abc, get a, b, c in each iteration
        for(let letter of map[digits[i]]) {
            // s + current letter, i + 1 move to next digits
            dfs(s + letter, i + 1)
        }
    }
    
    // initialize to empty and 0 index
    dfs('', 0);
    return res;
};