17. Letter Combinations of a Phone Number

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

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

class Solution {
private:
    const string digit2str[8] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public:
    inline int getTotalNum(string &digits) {
        int num = 1;
        for (const auto c: digits) num *= digit2str[c - '2'].size();
        return num;
    }
    vector<string> letterCombinations(string &digits) {
        vector<string> comb;
        if (digits.empty()) return comb;
        string str;
        comb.reserve(getTotalNum(digits));
        letterCombinations(digits, comb, str, 0);
        return comb;
    }
    void letterCombinations(string &digits, vector<string> &comb, string &str, int current) {
        if (current >= digits.size()) {
            comb.emplace_back(str);
            return;
        }
        for (const auto c: digit2str[digits[current] - '2']) {
            str.push_back(c);
            letterCombinations(digits, comb, str, current + 1);
            str.pop_back();
        }
    }
   
};

• #backtracking