967- letter combination of telephone number

Letter combination of telephone number

Given a number only 2-9 String , Returns all the letter combinations it can represent . You can press In any order return .

The mapping of numbers to letters is given as follows （ Same as phone key ）. Be careful 1 Does not correspond to any letter .

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”]

Tips ：

0 <= digits.length <= 4
digits[i] Is the scope of [‘2’, ‘9’] A number of .

Their thinking

First, use a hash table to store all possible letters corresponding to each number , And then do the backtracking operation .

Maintaining a string during backtracking , Represents an existing alphabetic arrangement （ If you don't traverse all the numbers of the phone number , The existing alphabetic arrangement is incomplete ）. The string is initially empty . Take one digit of the phone number at a time , Get all possible letters corresponding to the number from the hash table , And insert one of the letters after the existing alphabet , Then continue to process the last digit of the phone number , Until all the numbers in the phone number are processed , That is to get a complete alphabetic arrangement . And then go back , Traverse the rest of the alphabet .

Backtracking algorithm is used to find all feasible solutions , If a solution is found to be infeasible , It will abandon the infeasible solution . In this question , Because every letter corresponding to every number can enter the alphabet , So there is no infeasible solution , Just enumerate all the solutions directly .

Solution code

class Solution 
{
    
public:
    vector<string> letterCombinations(string digits) 
    {
    
        vector<string> combinations;
        if (digits.empty()) 
        {
    
            return combinations;
        }
        unordered_map<char, string> phoneMap
        {
    
            {
    '2', "abc"},
            {
    '3', "def"},
            {
    '4', "ghi"},
            {
    '5', "jkl"},
            {
    '6', "mno"},
            {
    '7', "pqrs"},
            {
    '8', "tuv"},
            {
    '9', "wxyz"}
        };
        string combination;
        backtrack(combinations, phoneMap, digits, 0, combination);
        return combinations;
    }

    void backtrack(vector<string>& combinations, 
        const unordered_map<char, string>& phoneMap, 
        const string& digits,
        int index, 
        string& combination) 
    {
    
        if (index == digits.length()) 
        {
    
            combinations.push_back(combination);
        }
        else 
        {
    
            char digit = digits[index];
            const string& letters = phoneMap.at(digit);
            for (const char& letter : letters) 
            {
    
                combination.push_back(letter);
                backtrack(combinations, phoneMap, digits, index + 1, combination);
                combination.pop_back();
            }
        }
    }
};