LeetCode Problem

Problem Description

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

Examples

Input: 23
Output: ad,ae,af,bd,be,bf,cd,ce,cf

Input:
Output:

Input: 2
Output: a,b,c

Constraints

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

Follow-up

Approach to Solve

Use backtracking to generate all possible combinations.

Code Implementation

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits: return []
        phone = {
            '2': ['a', 'b', 'c'],
            '3': ['d', 'e', 'f'],
            '4': ['g', 'h', 'i'],
            '5': ['j', 'k', 'l'],
            '6': ['m', 'n', 'o'],
            '7': ['p', 'q', 'r', 's'],
            '8': ['t', 'u', 'v'],
            '9': ['w', 'x', 'y', 'z']
        }
        def backtrack(index, path):
            if index == len(digits):
                combinations.append(''.join(path))
                return
            for letter in phone[digits[index]]:
                path.append(letter)
                backtrack(index + 1, path)
                path.pop()
        combinations = []
        backtrack(0, [])
        return combinations

class Solution {
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) return new ArrayList<>();
        Map<Character, String> phoneMap = new HashMap<>();
        phoneMap.put('2', "abc");
        phoneMap.put('3', "def");
        phoneMap.put('4', "ghi");
        phoneMap.put('5', "jkl");
        phoneMap.put('6', "mno");
        phoneMap.put('7', "pqrs");
        phoneMap.put('8', "tuv");
        phoneMap.put('9', "wxyz");
        List<String> combinations = new ArrayList<>();
        backtrack(combinations, phoneMap, digits, 0, new StringBuilder());
        return combinations;
    }
    private void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuilder path) {
        if (index == digits.length()) {
            combinations.add(path.toString());
            return;
        }
        String letters = phoneMap.get(digits.charAt(index));
        for (char letter : letters.toCharArray()) {
            path.append(letter);
            backtrack(combinations, phoneMap, digits, index + 1, path);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        vector<string> result;
        unordered_map<char, string> phone = {
            {'2', "abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"}
        };
        string path;
        backtrack(digits, 0, path, result, phone);
        return result;
    }
    void backtrack(const string& digits, int index, string& path, vector<string>& result, const unordered_map<char, string>& phone) {
        if (index == digits.length()) {
            result.push_back(path);
            return;
        }
        for (char c : phone.at(digits[index])) {
            path.push_back(c);
            backtrack(digits, index + 1, path, result, phone);
            path.pop_back();
        }
    }
};

Explanation

The Letter Combinations of a Phone Number problem is solved using a backtracking approach. Here's a detailed explanation of the solution:

First, we create a mapping of digits to their corresponding letters on a phone keypad. This is typically stored in a dictionary or map.
We use a recursive backtracking function that takes the following parameters:
- index: the current position in the input string
- path: the current combination being built
- result: the list to store all valid combinations
The base case for the recursion is when the index reaches the end of the input string. At this point, we've built a complete combination, so we add it to the result.
In the recursive step:
- We get the letters corresponding to the current digit.
- For each letter, we: a) Add it to the current path b) Recursively call the function with the next index c) Remove the letter from the path (backtrack)
This process ensures that we explore all possible combinations.
Time Complexity: O(4^n), where n is the length of the input string.
- In the worst case (digits 7 or 9), each digit corresponds to 4 letters.
- We have n levels of recursion, and at each level, we make up to 4 recursive calls.
Space Complexity: O(n)
- The recursion stack can go n levels deep in the worst case.
- The space needed to store the result is not counted in space complexity analysis.
Edge Cases:
- If the input string is empty, we return an empty list.
Optimizations:
- We can use a StringBuilder (in Java) or a mutable string (in Python) to build the combinations more efficiently.
- In languages like C++, we can pass the result vector by reference to avoid copying.

This approach efficiently generates all possible letter combinations for the given input digits, handling the varying number of letters per digit and exploring all possibilities through backtracking.

Complexity

Time Complexity: O(4^n)
Space Complexity: O(n)