Letter Combinations of a Phone Number | Leetcode 17 | Optimal Solution in Python

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 given below. Note that 1 does not map to any letters.

Here’s the [Problem Link] to begin with.

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

Solution: Backtracking Approach

Intuition

Think of this like dialing a phone number where each digit has multiple letter options, and you want to try every possible word you could spell! Imagine you have an old phone keypad where pressing “2” could give you ‘a’, ‘b’, or ‘c’, and pressing “3” could give you ‘d’, ‘e’, or ‘f’. If you press “23”, you want to know all possible 2-letter combinations you could spell.

The key insight is that this is a tree exploration problem. For each digit position, we have multiple choices (letters), and we need to explore all possible paths through this tree. It’s like having a decision tree where at each level (digit position), you branch out to try all possible letters for that digit.

For example, with “23”:

      Root
    /   |   \
   a    b    c    (choices for digit '2')
  /|\  /|\  /|\
 d e f d e f d e f (choices for digit '3')

Each path from root to leaf gives us one valid combination.

Detailed Approach

1. Setup Digit-to-Letter Mapping: Create a dictionary that maps each digit to its corresponding letters, just like a phone keypad.
2. Base Case: When we’ve processed all digits (index == len(digits)), we’ve formed a complete combination, so add it to our result.
3. Recursive Choice: For the current digit at index, get all possible letters it can represent. For each letter, make a recursive call to process the next digit, building the current string as we go.
4. String Building: Instead of maintaining a list and popping (like in subset problems), we build the string by concatenation since strings are immutable in Python – this naturally handles the “backtracking” for us.
5. Edge Case: Handle empty input by returning empty list immediately.

Code

class Solution:
    def __init__(self):
        # Phone keypad mapping - same as traditional phone buttons
        self.digits_to_letters = {
            "2": "abc",
            "3": "def", 
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }

    def helper(self, digits, ans, index, current):
        # Base case: processed all digits, we have a complete combination
        if index == len(digits):
            ans.append(current)  # Add the complete combination to results
            return

        # Get all possible letters for the current digit
        letters = self.digits_to_letters.get(digits[index], "")
        
        # Try each possible letter for this digit position
        for letter in letters:
            # Recursive call: move to next digit, extend current combination
            self.helper(digits, ans, index + 1, current + letter)

    def letterCombinations(self, digits):
        ans = []
        # Handle edge case: empty input
        if not digits:
            return ans
        
        # Start the backtracking process
        self.helper(digits, ans, 0, "")  # index=0, current=""
        return ans

Code Explanation

The solution uses backtracking with string concatenation. The digits_to_letters dictionary mimics a phone keypad mapping. The helper function is the core recursive backtracking function:

• Parameters:
  • digits: input string of digits
  • ans: result list to collect all combinations
  • index: current position in digits string
  • current: current combination being built
• Base Case: When index == len(digits), we’ve made choices for all digits, so current contains a complete valid combination.
• Recursive Case: Get all letters for digits[index], and for each letter, recursively solve for the remaining digits with the updated combination string.

The beauty of using string concatenation (current + letter) is that it naturally creates a new string for each recursive branch, eliminating the need for explicit backtracking (no need to “undo” changes like with lists).

Dry Run

Let’s trace through: digits = "23"

graph TD
    Root["helper(digits='23', index=0, current='')<br/>Generate all letter combinations"]
    
    %% Level 0: index=0, digit='2', letters='abc'
    Root --- A["Try 'a'<br/>current='a'<br/>index=1"]
    Root --- B["Try 'b'<br/>current='b'<br/>index=1"]
    Root --- C["Try 'c'<br/>current='c'<br/>index=1"]
    
    %% Level 1 from 'a': index=1, digit='3', letters='def'
    A --- A1["Try 'd'<br/>current='ad'<br/>index=2"]
    A --- A2["Try 'e'<br/>current='ae'<br/>index=2"]
    A --- A3["Try 'f'<br/>current='af'<br/>index=2"]
    
    %% Level 1 from 'b': index=1, digit='3', letters='def'
    B --- B1["Try 'd'<br/>current='bd'<br/>index=2"]
    B --- B2["Try 'e'<br/>current='be'<br/>index=2"]
    B --- B3["Try 'f'<br/>current='bf'<br/>index=2"]
    
    %% Level 1 from 'c': index=1, digit='3', letters='def'
    C --- C1["Try 'd'<br/>current='cd'<br/>index=2"]
    C --- C2["Try 'e'<br/>current='ce'<br/>index=2"]
    C --- C3["Try 'f'<br/>current='cf'<br/>index=2"]
    
    %% Level 2: Base case - index == len(digits)
    A1 --- Result1["index=2 == len(digits)<br/>✅ Add 'ad' to result"]
    A2 --- Result2["index=2 == len(digits)<br/>✅ Add 'ae' to result"]
    A3 --- Result3["index=2 == len(digits)<br/>✅ Add 'af' to result"]
    
    B1 --- Result4["index=2 == len(digits)<br/>✅ Add 'bd' to result"]
    B2 --- Result5["index=2 == len(digits)<br/>✅ Add 'be' to result"]
    B3 --- Result6["index=2 == len(digits)<br/>✅ Add 'bf' to result"]
    
    C1 --- Result7["index=2 == len(digits)<br/>✅ Add 'cd' to result"]
    C2 --- Result8["index=2 == len(digits)<br/>✅ Add 'ce' to result"]
    C3 --- Result9["index=2 == len(digits)<br/>✅ Add 'cf' to result"]
    
    %% Final result
    Result1 --- Final["Final Result:<br/>['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']"]
    Result2 --- Final
    Result3 --- Final
    Result4 --- Final
    Result5 --- Final
    Result6 --- Final
    Result7 --- Final
    Result8 --- Final
    Result9 --- Final

    %% Styling
    style Result1 fill:#90EE90
    style Result2 fill:#90EE90
    style Result3 fill:#90EE90
    style Result4 fill:#90EE90
    style Result5 fill:#90EE90
    style Result6 fill:#90EE90
    style Result7 fill:#90EE90
    style Result8 fill:#90EE90
    style Result9 fill:#90EE90
    style Final fill:#90EE90
    
    style Root fill:#E6E6FA

For detailed dry run [Click here]

Time and Space Complexity

• Time Complexity: O(4^n × n) where n is the length of digits
  • 4^n because in worst case each digit maps to 4 letters (like ‘7’ and ‘9’)
  • The ×n factor comes from string concatenation operations
  • Total combinations = product of lengths of all digit mappings
• Space Complexity: O(n) for recursion stack depth
  • Plus O(4^n × n) for storing all result combinations
  • Each combination string has length n

Simplifying It

This approach is like systematically trying every possible word you could spell on an old phone by pressing the number keys. You go digit by digit, and for each digit, you try every letter it could represent. You build up your word letter by letter, and when you’ve used all the digits, you write down the complete word you spelled. The recursion naturally explores all possible “spelling paths” through your sequence of digit presses.

The key insight is recognizing this as a Cartesian product problem, we want all combinations where we pick one letter from each digit’s letter set. Backtracking is the perfect tool for systematically generating such combinations!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.