17. Letter Combinations of a Phone Number

• Difficulty: Medium

• Topics: String, Backtracking

• Similar Questions:

  • Generate Parentheses

  • Combination Sum

  • Binary Watch

Problem:

Given a string containing digits from 2-9 inclusive, 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:

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

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

Solutions:

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> ret;
        if (digits.length() == 0)   return ret;
        int pos = 0;
        string path;
        dfs(digits, pos, path, ret);
        return ret;
    }

    void dfs(string digits, int pos, string& path, vector<string>& ret) {
        if (pos == digits.length()) {
            ret.push_back(path);
            return;
        }

        char digit = digits[pos];
        for (auto c : numToLetters[digit]) {
            path.push_back(c);
            dfs(digits, pos + 1, path, ret);
            path.pop_back();
        }
    }

private:
    unordered_map<char, string> numToLetters {
            {'2', "abc"}, 
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"}
        };
};