17. Letter Combinations of a Phone Number (Medium)

Problem

Given a string of digits 2-9, return all possible letter combinations the digits could represent on a standard phone keypad. 1 has no letters; 0 is not in the input.

2: "abc", 3: "def", 4: "ghi", 5: "jkl",
6: "mno", 7: "pqrs", 8: "tuv", 9: "wxyz"

Example

• digits = "23" → ["ad","ae","af","bd","be","bf","cd","ce","cf"]
• digits = "" → []
• digits = "2" → ["a","b","c"]

LeetCode 17 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Iterative cartesian product

Build combinations digit-by-digit, extending each partial string with each letter of the next digit.

Python

def letter_combinations(digits):
    if not digits:
        return []
    mapping = {"2":"abc","3":"def","4":"ghi","5":"jkl",
               "6":"mno","7":"pqrs","8":"tuv","9":"wxyz"}
    result = [""]
    for d in digits:                                     # L1: loop over n digits
        result = [prefix + ch for prefix in result for ch in mapping[d]]  # L2: extend each combo
    return result

TypeScript

function letterCombinations(digits: string): string[] {
    if (!digits) return [];
    const mapping: Record<string, string> = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz',
    };
    let result: string[] = [''];
    for (const d of digits) {                                      // L1: loop over n digits
        const next: string[] = [];
        for (const prefix of result) {
            for (const ch of mapping[d]) {
                next.push(prefix + ch);                            // L2: O(k^n · n) total
            }
        }
        result = next;
    }
    return result;
}

Go

func letterCombinations(digits string) []string {
    if len(digits) == 0 {
        return []string{}
    }
    mapping := map[byte]string{
        '2': "abc", '3': "def", '4': "ghi", '5': "jkl",
        '6': "mno", '7': "pqrs", '8': "tuv", '9': "wxyz",
    }
    result := []string{""}
    for i := 0; i < len(digits); i++ {            // L1: loop over n digits
        letters := mapping[digits[i]]
        next := []string{}
        for _, prefix := range result {
            for _, ch := range letters {
                next = append(next, prefix+string(ch)) // L2: O(k^n · n) total
            }
        }
        result = next
    }
    return result
}

Where the time goes, line by line

Variables: n = len(digits), k = average letters per digit (3 or 4).

Line	Per-call cost	Times executed	Contribution
L1 (outer loop)	$O(1)$ overhead	n	$O(n)$
L2 (list comprehension)	$O(k · \|result\|)$	n	$O(k^n · n)$ ← dominates

After processing digit i, result has k^i entries each of length i. The comprehension at step i processes k^(i-1) × k entries. Total work is the sum over i of i × k^i = $O(n · k^n)$.

Complexity

• Time: $O(4^n · n)$ worst case, driven by L2 growing result at every step.
• Space: $O(4^n · n)$ for the output.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    func letterCombinations(_ digits: String) -> [String] {
        let map: [Character: [Character]] = ["2": Array("abc"), "3": Array("def"), "4": Array("ghi"), "5": Array("jkl"), "6": Array("mno"), "7": Array("pqrs"), "8": Array("tuv"), "9": Array("wxyz")]
        var combinations = [""]
        for digit in digits { var next: [String] = []; for prefix in combinations { for letter in map[digit]! { next.append(prefix + String(letter)) } }; combinations = next }
        return digits.isEmpty ? [] : combinations
    }
}

Approach 2: Backtracking DFS (canonical)

Recursively build one combination at a time.

Python

def letter_combinations(digits):
    if not digits:
        return []
    mapping = {"2":"abc","3":"def","4":"ghi","5":"jkl",
               "6":"mno","7":"pqrs","8":"tuv","9":"wxyz"}
    result = []
    path = []

    def backtrack(i):
        if i == len(digits):
            result.append("".join(path))  # L1: O(n) join when complete
            return
        for ch in mapping[digits[i]]:     # L2: loop over letters for digit i
            path.append(ch)               # L3: O(1) push
            backtrack(i + 1)              # L4: recurse
            path.pop()                    # L5: O(1) pop

    backtrack(0)
    return result

TypeScript

function letterCombinations(digits: string): string[] {
    if (!digits) return [];
    const mapping: Record<string, string> = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz',
    };
    const result: string[] = [];
    const path: string[] = [];

    function backtrack(i: number): void {
        if (i === digits.length) {
            result.push(path.join(''));   // L1: O(n) join when complete
            return;
        }
        for (const ch of mapping[digits[i]]) {  // L2: loop over letters for digit i
            path.push(ch);                        // L3: O(1) push
            backtrack(i + 1);                     // L4: recurse
            path.pop();                           // L5: O(1) pop
        }
    }

    backtrack(0);
    return result;
}

Go

func letterCombinations(digits string) []string {
    if len(digits) == 0 {
        return []string{}
    }
    mapping := map[byte]string{
        '2': "abc", '3': "def", '4': "ghi", '5': "jkl",
        '6': "mno", '7': "pqrs", '8': "tuv", '9': "wxyz",
    }
    result := []string{}
    path := []byte{}

    var backtrack func(i int)
    backtrack = func(i int) {
        if i == len(digits) {
            result = append(result, string(path)) // L1: O(n) join when complete
            return
        }
        for _, ch := range mapping[digits[i]] { // L2: loop over letters for digit i
            path = append(path, byte(ch))        // L3: O(1) push
            backtrack(i + 1)                     // L4: recurse
            path = path[:len(path)-1]            // L5: O(1) pop
        }
    }

    backtrack(0)
    return result
}

Where the time goes, line by line

Variables: n = len(digits), k = average letters per digit (3 or 4).

Line	Per-call cost	Times executed	Contribution
L1 (join + append)	$O(n)$	k^n leaves	$O(k^n · n)$
L2 (letter loop)	$O(1)$	k^n total	$O(k^n)$
L3/L4/L5 (push/recurse/pop)	$O(1)$	k^n · n	$O(k^n · n)$ ← dominates

The recursion tree has k^n leaves (one per combination) and n levels. Most work is at the leaves.

Complexity

• Time: $O(4^n · n)$, driven by L1/L4 building k^n combinations of length n.
• Space: $O(n)$ recursion + output.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    func letterCombinations(_ digits: String) -> [String] {
        let map: [Character: [Character]] = ["2": Array("abc"), "3": Array("def"), "4": Array("ghi"), "5": Array("jkl"), "6": Array("mno"), "7": Array("pqrs"), "8": Array("tuv"), "9": Array("wxyz")]
        let values = Array(digits); if values.isEmpty { return [] }; var result: [String] = []
        func search(_ index: Int, _ current: [Character]) { if index == values.count { result.append(String(current)); return }; for letter in map[values[index]]! { search(index + 1, current + [letter]) } }
        search(0, []); return result
    }
}

Approach 3: itertools.product

Python one-liner using the standard library.

from itertools import product

def letter_combinations(digits):
    if not digits:
        return []
    mapping = {"2":"abc","3":"def","4":"ghi","5":"jkl",
               "6":"mno","7":"pqrs","8":"tuv","9":"wxyz"}
    return ["".join(p) for p in product(*(mapping[d] for d in digits))]  # L1: O(k^n · n)

Where the time goes, line by line

Variables: n = len(digits), k = average letters per digit (3 or 4).

Line	Per-call cost	Times executed	Contribution
L1 (product + join)	$O(n)$ per combo	k^n	$O(k^n · n)$ ← dominates

Complexity

• Time: $O(4^n · n)$.
• Space: $O(4^n · n)$.

Production-correct; rarely accepted in an interview that wants the algorithm.

Swift

final class Solution {
    func letterCombinations(_ digits: String) -> [String] {
        let map: [Character: [String]] = ["2": ["a","b","c"], "3": ["d","e","f"], "4": ["g","h","i"], "5": ["j","k","l"], "6": ["m","n","o"], "7": ["p","q","r","s"], "8": ["t","u","v"], "9": ["w","x","y","z"]]
        if digits.isEmpty { return [] }
        return digits.reduce([""]) { partial, digit in partial.flatMap { prefix in map[digit]!.map { prefix + $0 } } }
    }
}

Summary

Approach	Time	Space
Iterative cartesian product	$O(4^n · n)$	$O(4^n · n)$
Backtracking DFS	$O(4^n · n)$	$O(n)$ recursion
itertools.product	$O(4^n · n)$	$O(4^n · n)$

All optimal in time. Backtracking is smallest in recursion-stack terms and is the “show you understand the algorithm” interview answer.

Test cases

Python

def letter_combinations(digits):
    if not digits:
        return []
    mapping = {"2":"abc","3":"def","4":"ghi","5":"jkl",
               "6":"mno","7":"pqrs","8":"tuv","9":"wxyz"}
    result = []
    path = []
    def backtrack(i):
        if i == len(digits):
            result.append("".join(path))
            return
        for ch in mapping[digits[i]]:
            path.append(ch)
            backtrack(i + 1)
            path.pop()
    backtrack(0)
    return result

def _run_tests():
    assert sorted(letter_combinations("23")) == sorted(["ad","ae","af","bd","be","bf","cd","ce","cf"])
    assert letter_combinations("") == []
    assert sorted(letter_combinations("2")) == ["a","b","c"]
    # digit 7 has 4 letters: pqrs
    assert sorted(letter_combinations("7")) == ["p","q","r","s"]
    # two-digit: 2+2 = 9 combinations
    assert len(letter_combinations("22")) == 9
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function letterCombinations(digits: string): string[] {
    if (!digits) return [];
    const mapping: Record<string, string> = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz',
    };
    const result: string[] = [];
    const path: string[] = [];
    function backtrack(i: number): void {
        if (i === digits.length) { result.push(path.join('')); return; }
        for (const ch of mapping[digits[i]]) {
            path.push(ch);
            backtrack(i + 1);
            path.pop();
        }
    }
    backtrack(0);
    return result;
}

console.assert(JSON.stringify(letterCombinations('23').sort()) ===
    JSON.stringify(['ad','ae','af','bd','be','bf','cd','ce','cf'].sort()));
console.assert(JSON.stringify(letterCombinations('')) === JSON.stringify([]));
console.assert(JSON.stringify(letterCombinations('2').sort()) === JSON.stringify(['a','b','c']));
console.assert(JSON.stringify(letterCombinations('7').sort()) === JSON.stringify(['p','q','r','s']));
console.assert(letterCombinations('22').length === 9);
console.log("all tests pass");

Go

func letterCombinations(digits string) []string {
    if len(digits) == 0 {
        return []string{}
    }
    mapping := map[byte]string{
        '2': "abc", '3': "def", '4': "ghi", '5': "jkl",
        '6': "mno", '7': "pqrs", '8': "tuv", '9': "wxyz",
    }
    result := []string{}
    path := []byte{}
    var backtrack func(i int)
    backtrack = func(i int) {
        if i == len(digits) {
            result = append(result, string(path))
            return
        }
        for _, ch := range mapping[digits[i]] {
            path = append(path, byte(ch))
            backtrack(i + 1)
            path = path[:len(path)-1]
        }
    }
    backtrack(0)
    return result
}

Related data structures

• Hash Tables, digit -> letters map
• Strings, output

Related concepts

• Permutations, the ordered arrangement pattern where position and used items define the search.
• Backtracking, the explore, undo, and prune pattern for building candidates.