17. Letter Combinations of a Phone Number

Description

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.

Intuition

Each digit corresponds to a set of letters. The problem is essentially about generating all combinations of these letters corresponding to the sequence of digits provided. This is a classic example of a combinatorial problem which can be solved using backtracking.

Approach

1. Mapping: Create a dictionary to map each digit to its respective letters.
2. Backtracking: Use a helper function to generate combinations. Start with an empty string and iterate through the digits. - For each digit, append each possible letter to the current combination and recurse for the next digit. - If the current combination has a length equal to the number of digits, add it to the results list.
3. Base Case: If the input digits string is empty, immediately return an empty list.

Complexity

Time Complexity:

(O(3^N \times 4^M)), where (N) is the number of digits that maps to 3 letters (like 2, 3, 4, 5, 6, 8) and (M) is the number of digits that maps to 4 letters (like 7, 9). This is because there are 3 possibilities for each of the (N) digits and 4 possibilities for each of the (M) digits.

Space Complexity:

(O(3^N \times 4^M)) for the output list, plus the recursion stack.

Code

C++

class Solution {
public:
    vector letterCombinations(string digits) {
        if (digits.empty()) return {};

        unordered_map keyboard = {
            {'2', "abc"}, {'3', "def"}, {'4', "ghi"},
            {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"},
            {'8', "tuv"}, {'9', "wxyz"}
        };

        vector output;
        function backtrack = [&](string current, int index) {
            if (index == digits.size()) {
                output.push_back(current);
                return;
            }
            string letters = keyboard[digits[index]];
            for (char letter : letters) {
                backtrack(current + letter, index + 1);
            }
        };
        backtrack("", 0);
        return output;
    }
};

Python

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

Java

class Solution {
    public List letterCombinations(String digits) {
        if (digits.isEmpty()) return new ArrayList<>();

        Map keyboard = new HashMap<>();
        keyboard.put('2', "abc");
        keyboard.put('3', "def");
        keyboard.put('4', "ghi");
        keyboard.put('5', "jkl");
        keyboard.put('6', "mno");
        keyboard.put('7', "pqrs");
        keyboard.put('8', "tuv");
        keyboard.put('9', "wxyz");

        List output = new ArrayList<>();
        backtrack(output, keyboard, digits, "", 0);
        return output;
    }

    private void backtrack(List output, Map keyboard, String digits, String current, int index) {
        if (index == digits.length()) {
            output.add(current);
            return;
        }
        String letters = keyboard.get(digits.charAt(index));
        for (char letter : letters.toCharArray()) {
            backtrack(output, keyboard, digits, current + letter, index + 1);
        }
    }
}

JavaScript

var letterCombinations = function (digits) {
    if (digits.length === 0) return [];

    const keyboard = {
        "2": "abc",
        "3": "def",
        "4": "ghi",
        "5": "jkl",
        "6": "mno",
        "7": "pqrs",
        "8": "tuv",
        "9": "wxyz"
    };

    const output = [];
    const backtrack = (current, index) => {
        if (index === digits.length) {
            output.push(current);
            return;}
        const letters = keyboard[digits[index]];
        for (let letter of letters) {
            backtrack(current + letter, index + 1);}
    };
    backtrack('', 0);
    return output;
};