Limited Time Offer:Up to 25% off Hello Interview Premium

⌘K

Tutor

Get Premium

Leetcode 17. Letter Combinations of a Phone Number

Given a string of digits 2–9, return all possible letter strings by mapping each digit to its phone-keypad letters — effectively computing the Cartesian product of per-digit letter sets; this is typically solved by DFS/backtracking to enumerate combinations (digits length ≤ 4).

Asked at:

Servicenow

Amazon

DESCRIPTION

Input:

digits = "23"

Output:

["ad","ae","af","bd","be","bf","cd","ce","cf"]

Explanation: Digit '2' maps to ['a','b','c'] and digit '3' maps to ['d','e','f']. All 9 combinations (3×3) are generated by pairing each letter from '2' with each letter from '3'

Constraints:

0 <= digits.length <= 4
digits[i] is a digit in the range ['2', '9']
Phone keypad mapping: 2→abc, 3→def, 4→ghi, 5→jkl, 6→mno, 7→pqrs, 8→tuv, 9→wxyz

Understanding the Problem

Let's understand what we're being asked to do. We have a string of digits like '23' and need to generate all possible letter combinations based on phone keypad mappings.

Tracing through '23': digit '2' maps to letters ['a','b','c'] and digit '3' maps to ['d','e','f']. We need all combinations: 'ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf' - that's 9 total combinations (3 × 3).

Important constraint: Each digit maps to 3-4 letters (digit '7' and '9' have 4 letters each). The input string length is at most 4, so we won't have an explosion of combinations.

Edge cases to consider: What if the input is empty? (return empty list). What if input has only one digit? (return all letters for that digit). The problem guarantees digits are only 2-9, so no need to handle '0' or '1'.

Building Intuition

For each digit in the input, we need to choose one letter from its mapping. If we have 2 digits, we make 2 choices. If we have 3 digits, we make 3 choices.

This is a decision tree where at each level, we branch into multiple possibilities (one branch per letter option). Each path from root to leaf represents one valid combination.

By exploring all possible paths through this decision tree, we systematically generate every combination without missing any or creating duplicates.

The total number of combinations is the product of the number of letters for each digit. For '23': 3 letters × 3 letters = 9 combinations. For '234': 3 × 3 × 3 = 27 combinations.

Think of building a combination step-by-step, like filling in blanks: _ _ _ for input '234'.

For the first blank, try 'a' (from digit '2'), then recursively fill the remaining blanks. When you've filled all blanks, you have one complete combination. Then backtrack - undo the last choice and try the next option ('b', then 'c'). This explore-and-backtrack pattern naturally generates all combinations.

Common Mistakes

Forgetting to backtrack: After exploring one branch, you must remove the last added letter before trying the next option. Without backtracking, you'll build incorrect combinations like 'abc' instead of separate 'a', 'b', 'c' paths.

Not handling empty input: The edge case of empty string should return an empty list, not a list containing an empty string. Check for this before starting recursion.

Incorrect base case: The recursion should stop when current combination length equals digits length, not when you've processed all letters. The base case is about the combination being complete, not about exhausting options.

Inefficient string concatenation: In languages like Java, repeatedly concatenating strings creates new objects. Use StringBuilder or pass indices instead of building strings at each step.

Off-by-one errors in indexing: Make sure the current digit index matches the current combination length. If you're building combination 'ad', you should be processing digits[2] next, not digits[1].

Optimal Solution

Use depth-first search with backtracking to explore all possible letter combinations. Start with an empty string and recursively add one letter at a time from each digit's mapping. When the current combination length equals the input digits length, we've found a complete combination - add it to results. Then backtrack by removing the last letter and trying the next option. This systematically explores the entire decision tree of letter choices.

Visualization

def letter_combinations(digits):
    """
    Generate all possible letter combinations from phone keypad digits.
    Uses DFS/backtracking to explore all combinations.
    """
    if not digits:
        return []
    
    # Phone keypad mapping
    phone_map = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    }
    
    result = []
    current = []
    
    def backtrack(index):
        # Base case: combination complete
        if index == len(digits):
            result.append(''.join(current))
            return
        
        # Get letters for current digit
        letters = phone_map[digits[index]]
        
        # Try each letter
        for letter in letters:
            # Choose: add letter to current combination
            current.append(letter)
            
            # Explore: recurse to next digit
            backtrack(index + 1)
            
            # Unchoose: backtrack by removing letter
            current.pop()
    
    # Start DFS from first digit
    backtrack(0)
    
    return result

Start letter combinations generation

0 / 101

Test Your Knowledge

Complexity Analysis

Time Complexity: O(4^n × n) In the worst case (all digits are 7 or 9), each digit has 4 letter choices, giving 4^n combinations where n is the input length. For each combination, we spend O(n) time building the string. Since n ≤ 4, this is effectively O(4^4) = O(256) combinations maximum.

Space Complexity: O(n) The recursion depth is at most n (one level per digit), and we store the current combination string of length n. The output list size is not counted in auxiliary space complexity.

What We've Learned

backtracking mastery: Understanding when and why to use backtracking data structure for this type of problem pattern
Algorithm optimization: Recognizing how to achieve O(4^n × n) time complexity through efficient problem decomposition
Implementation patterns: Learning the key coding techniques that make this solution robust and maintainable
Problem-solving approach: Developing intuition for when to apply this algorithmic pattern to similar challenges
Performance analysis: Understanding the time and space complexity trade-offs and why they matter in practice

Test Your Understanding

Why is backtracking the right data structure for this problem?

backtracking provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Mid October, 2025

Mid-level

Early October, 2025

Mid-level

Early September, 2025

Mid-level

Get Premium to View All 6 Reports

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 17. Letter Combinations of a Phone Number

DESCRIPTION

Understanding the Problem

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact