17. 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.

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:

• 1 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9'].

Approach 01: Backtracking

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

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits: return []
        mapping = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
        res = []
        def backtrack(idx, current):
            if idx == len(digits):
                res.append("".join(current))
                return
            for char in mapping[digits[idx]]:
                current.append(char)
                backtrack(idx + 1, current)
                current.pop()
        backtrack(0, [])
        return res

class Solution {
    private String[] mapping = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List letterCombinations(String digits) {
        List res = new ArrayList<>();
        if (digits.length() == 0) return res;
        backtrack(digits, 0, new StringBuilder(), res);
        return res;
    }
    private void backtrack(String digits, int idx, StringBuilder current, List res) {
        if (idx == digits.length()) {
            res.add(current.toString());
            return;
        }
        String letters = mapping[digits.charAt(idx) - '0'];
        for (char c : letters.toCharArray()) {
            current.append(c);
            backtrack(digits, idx + 1, current, res);
            current.deleteCharAt(current.length() - 1);
        }
    }
}