Letter Combinations of a Phone Number

Backtracking/Bruteforce builder

Problem

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.

For example:

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

Input: digits = "2"
Output: ["a","b","c"]

Thought Process

• How can we map the letters to the numbers? With a dictionary?

  • Yes. We can map each letter to it's corresponding numbers and in out for-loop we refernce the number key in the dictionary so we can loop through the letters. We DO NOT loop through the numbers

• We DO NOT loop through the numbers. We only loop through the letters of the numbers. To handle "looping" through the numbers, in our recursion method we just call on the next number in the input digit with digit[1: ]. This retrieves the next digit and the for-loop will iterate through it's characters.

Solution

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if digits == "":
            return []
        
        letters = {
            "0":"0",
            "1":"1",
            "2":"abc",
            "3":"def",
            "4":"ghi",
            "5":"jkl",
            "6":"mno",
            "7":"pqrs",
            "8":"tuv",
            "9":"wxyz",
        }
        
        soln = []
        self.helper(digits, letters,"", soln)
        return soln
    
    def helper(self,digits,letters, comb, soln):
        if len(digits) == 0:
            soln.append(comb)
            return 
        
        chars = letters[digits[0]]
        
        for i in chars:
            comb+=i
            self.helper(digits[1:],letters,comb,soln)
            comb = comb[:-1]
        

Key Points

• We use a dictionary in order to map the letters to the numbers

• It is important you realize, again, we DO NOT loop through the numbers. We only loop through the letters which we retrieve from the dictionary with the number as key.

Time Complexity

• Time:$O(n* 4^n)$ because at most there will be $4^n$forks (because of the letters in 7 and 9 on the phone) and it will be done n times for each number given (see the Thought Process picture above)

• Space: $O(4^n)$ is the most calls the recursion stack will use