#78 Medium Time O(4^n) Space O(n) Animated

Letter Combinations of a Phone Number

Return all possible letter combinations from phone digits.

LeetCode ↗

Tutor Mode Build the mental model before you memorize the code.

1 Predict
2 Trace
3 Explain
4 Implement

Pattern Backtracking: choose, explore, unchoose

Build one partial answer at a time and undo each choice so sibling branches start clean.

Approach: DFS (Backtracking)

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Core Insight

Build one partial answer at a time and undo each choice so sibling branches start clean.

Common Pitfall

Copy a completed path before appending it to results; later mutations must not alter it.

Description

Return all possible letter combinations from phone digits.

Constraints

Time Complexity: O(4^n)
Space Complexity: O(n)

Solution — DFS (Backtracking)

TimeO(4^n) SpaceO(n)

Implementation Plan

Translate the invariant into these small, testable moves.

Choose a candidate.
Record the choice.
Explore the next decision.
Undo the choice before trying the next candidate.

def letterCombinations(digits):
    res = []
    digitToChar = {
        "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
        "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"
    }
    
    def backtrack(i, curStr):
        if len(curStr) == len(digits):
            res.append(curStr)
            return
        for c in digitToChar[digits[i]]:
            backtrack(i + 1, curStr + c)
            
    if digits:
        backtrack(0, "")
    return res

Palindrome Partitioning

N-Queens

Letter Combinations of a Phone Number

Steps

Description

Constraints

Tags

Solution — DFS (Backtracking)