Link to Question

MEDIUM

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 digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Digit	Letters
2	abc
3	def
4	ghi
5	jkl
6	mno
7	pqrs
8	tuv
9	wxyz

Example

Input:

digits = "23"

Output:

["ad","ae","af","bd","be","bf","cd","ce","cf"]

Explanation:
The digit '2' maps to "abc", and '3' maps to "def". All combinations are returned.

---

Constraints

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

---

Solution: Backtracking

• Time Complexity: O(3ⁿ × 4ᵐ), where n is the number of digits that map to 3 letters and m is the number that map to 4 letters.
• Space Complexity: O(3ⁿ × 4ᵐ)

C++

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        vector<string> res;
        vector<string> phone = {"",    "",    "abc", "def", "ghi", "jkl",
                                "mno", "pqrs", "tuv", "wxyz"};
        string path;
        function<void(int)> backtrack = [&](int idx) {
            if (idx == digits.size()) {
                res.push_back(path);
                return;
            }
            for (char c : phone[digits[idx] - '0']) {
                path.push_back(c);
                backtrack(idx + 1);
                path.pop_back();
            }
        };
        backtrack(0);
        return res;
    }
};