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.

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:

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

Explanation

First, build a map that stores relationships between numbers and the letters they represent.

Then, use depth-first seach approach to find all letter 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]:
        result = []
        
        if digits == None or digits == "": 
            return result
    
        letters = {
            '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(digits, "", letters, result)
        
        return result
    
    def helper(self, digits, combination, letters, result):

        if len(combination) == len(digits):
            result.append(combination) 
            return 
        
        for char in letters[digits[len(combination)]]:

            
            combination += char
            
            self.helper(digits, combination, letters, result)
            
            combination = 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.

3 Thoughts to “LeetCode 17. Letter Combinations of a Phone Number”

  1. bro i am not good at recursion . Could you please explain it in betterways? how sb.length works here or how the combinations is happening???
    plz leave a reply.

  2. Hello, how can I reach you privately?
    my email is ljustincoder@gmail.com. I need help in understanding some of your solutions.
    Secondly, regarding the letter combinations of a phone number. I understand what your code does but my recursion skill is weak and need clarity on one condition. So, say digit is “23”. the first time the helper is called. sb is “”. but what is the index of “”? how did the computer know that when you do :
    lettersMap.get(digits.charAt(sb.length())), it is to get the the index 2? is “” equated to 0?

    then, it gets the first character in the key 2 and appends it to the StringBuilder making the sb.length=1. Ok. I get it, it picks the map with key index 1 which is 3 and begins to add its’ characters. and each time the sb.length==digit.length, it adds the StringBuilder to the result list. and then removes that character. it continues until even the character a from the phone number 2 is removed, defaulting the StringBuilder sb to “” again. at this stage, the result is “ad, ae, af”.
    Now, this is where I don’t understand it. Because instead of picking character a again, it picks b. how was the programme able to know that the first character in phone number key 2, which is ‘a’ should be overlooked?

    This is what I don’t get.

    Lastly, have you considered setting up a patron page where people like me can donate something, no matter how small, to encourage you? I am glued to your youtube videos and seriously testing the codes to make sense of your thought processes. Please, don’t stop. You are the only one explaining it simplistically. Is there a way to also send you Leetcode questions I find challenging so you can solve and explain to the community?

Leave a Reply

Your email address will not be published. Required fields are marked *