Letter Combinations of a Phone Number | Leetcode 17

Welcome to our multi-language deep dive on Letter Combinations of a Phone Number (Leetcode 17). This problem visually simulates older T9 texting mechanisms found on vintage flip phones. It is universally used in interviews to evaluate your core understanding of DFS Backtracking and String Combinatorics.

Problem Statement

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 provided below. Note that 1 does not map to any letters. 2:"abc", 3:"def", 4:"ghi", 5:"jkl", 6:"mno", 7:"pqrs", 8:"tuv", 9:"wxyz"

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

Example 2: digits = "" => Output: []

Approach 1: Recursive DFS Backtracking

Generating all possible combinations implicitly requires evaluating a dynamic Cartesian Product (pairing each layer of children against all subsequent layers of children). The cleanest native way to build this is a Depth-First-Search (DFS) that utilizes "Backtracking".

We maintain a dynamic current_string variable.

1. We check the current digit in our input recursively.
2. We iterate over all 3 or 4 possible letters corresponding to that digit.
3. For each letter, we stick it physically onto the end of our current_string, and then recursively plunge down to the next digit.
4. Once our string reaches the target digits length, we append it to our Master Results Array, and "Backtrack" (by popping that letter back off) so the recursion tree can natively pivot to evaluate the next branched letter slot!

graph TD
    A["Input: '23'"] --> B["Start '2' ('abc')"]
    
    B --> C["Path 'a'"]
    B --> D["Path 'b'"]
    B --> E["Path 'c'"]
    
    C --> F["Next '3' ('def')"]
    F --> G("'ad'")
    F --> H("'ae'")
    F --> I("'af'")
    
    D -.-> J["... 'bd', 'be', 'bf'"]
    E -.-> K["... 'cd', 'ce', 'cf'"]

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        res = []
        if not digits:
            return res
            
        # Hardcode the T9 dictionary constraints
        digitToChar = {
            "2": "abc", "3": "def", 
            "4": "ghi", "5": "jkl", 
            "6": "mno", "7": "pqrs", 
            "8": "tuv", "9": "wxyz"
        }
        
        def backtrack(i, curStr):
            # Base Case: We hit the end of the digits loop!
            if len(curStr) == len(digits):
                res.append(curStr)
                return
                
            # Grab all letters tied to our current target digit string depth
            letters = digitToChar[digits[i]]
            for char in letters:
                # Branch dynamically recursively
                backtrack(i + 1, curStr + char)
                
        if digits:
            backtrack(0, "")
            
        return res

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (17)