LeetCode 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 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'].

Explanation

First, build a mapping between numbers and the letters they represent.

Then, use the backtracking approach to generate all possible combinations.

Java Solution

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        
        if (digits == null || digits.equals("")) {
            return result;
        }
        
        StringBuilder sb = new StringBuilder();
        
        Map<Character, char[]> lettersMap = getLettersMap();    

        letterCombinationsHelper(digits, sb, lettersMap, result);
        
        return result;
    }
    
    private Map<Character, char[]> getLettersMap() {
        Map<Character, char[]> lettersMap = new HashMap<>();
        lettersMap.put('0', new char[]{});
        lettersMap.put('1', new char[]{});                
        lettersMap.put('2', new char[]{'a', 'b', 'c'});                
        lettersMap.put('3', new char[]{'d', 'e', 'f'});                
        lettersMap.put('4', new char[]{'g', 'h', 'i'});    
        lettersMap.put('5', new char[]{'j', 'k', 'l'});    
        lettersMap.put('6', new char[]{'m', 'n', 'o'});    
        lettersMap.put('7', new char[]{'p', 'q', 'r', 's'});    
        lettersMap.put('8', new char[]{'t', 'u', 'v'});    
        lettersMap.put('9', new char[]{'w', 'x', 'y', 'z'});    
        
        return lettersMap;
    }
    
    private void letterCombinationsHelper(String digits, StringBuilder sb, Map<Character, char[]> lettersMap, List<String> result) {
        if (sb.length() == digits.length()) {
            result.add(sb.toString());
            return;
        }      
        
        for (char ch : lettersMap.get(digits.charAt(sb.length()))) {
            sb.append(ch);
            letterCombinationsHelper(digits, sb, lettersMap, result);            
            sb.deleteCharAt(sb.length() - 1);
        }        
    }
}

Python Solution

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        results = []
        
        if not digits:
             return results
            
        mapping = {
            "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"],            
        }
 

    
        self.helper(results, "", digits, mapping)
        

        return results
    
    
    def helper(self, results, combination, digits, mapping):
        if len(combination) == len(digits):
            results.append(combination)
            return
        
        
        letters = mapping[digits[len(combination)]]        
        
        for letter in letters:
            combination += letter

            self.helper(results, combination, digits, mapping)

            combination = combination[: len(combination) -1]
        
        

• Time complexity: O(3^N×4^M) where N is the number of digits in the input that maps to 3 letters (e.g. 2, 3, 4, 5, 6, 8) and M is the number of digits in the input that maps to 4 letters (e.g. 7, 9), and N+M is the total number digits in the input.
• Space complexity: O(3^N×4^M) since one has to keep 3^N times 4^M solutions.