Letter Combinations of a Phone Number

BacktrackingRecursion

20 min

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.

Example

Example 1:

Input: digits = "23"

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

Solution

This is a classic backtracking problem. We can map each digit to its corresponding letters. Then, we use a recursive function to explore all possible combinations. The function will take the current index of the digits string and the combination built so far.

Algorithm Steps

Create a mapping from digits to letters (e.g., a hash map or an array).
Define a recursive function `backtrack(index, currentString)`.
If `currentString` has the same length as the input `digits`, we've formed a complete combination. Add it to our results and return.
Get the letters corresponding to the digit at the current `index`.
Iterate through these letters:
- Append the letter to `currentString`.
- Recursively call `backtrack(index + 1, currentString)`.
- Backtrack: remove the letter from `currentString`.
Initial call: `backtrack(0, "")`.

Letter Combinations Visualization

Step-by-step backtracking algorithm

Progress1 / 1

Ready to start the visualization

Input Digits

Current Combination

Resulting Combinations

No solutions found yet...

Letter Combinations Solution


class Solution:
    def letterCombinations(self, digits: str) -> list[str]:
        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