Letter Combinations of a Phone Number

Mediumbacktrackingstring
Category: Backtracking
Companies that ask this question:
AmazonFacebookGoogleMicrosoftUber
LeetCode →NeetCode →

Approach

Letter Combinations of a Phone Number

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.

A mapping of digits to letters (just like on the telephone buttons) is given below:

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

Examples

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"]

Intuition

Classic Cartesian Product: For each digit, choose one of its letters.

For "23":

  • Digit 2: (a, b, c)
  • Digit 3: (d, e, f)
  • Combinations: a with each of (d,e,f), b with each of (d,e,f), c with each of (d,e,f) = 9 total

Backtracking approach: Build combinations character by character.

Pattern Recognition

This is a Backtracking with Mapping problem:

  • Map digits to letters
  • Explore all combinations
  • Build strings progressively

Approach

phone = {
  '2': 'abc', '3': 'def', '4': 'ghi',
  '5': 'jkl', '6': 'mno', '7': 'pqrs',
  '8': 'tuv', '9': 'wxyz'
}

def backtrack(index, current):
  if index == len(digits):
    result.append(current)
    return

  for letter in phone[digits[index]]:
    backtrack(index + 1, current + letter)

Complexity Analysis

  • Time: O(4^n × n) where n = digits length

    • Max 4 letters per digit (7 and 9)
    • O(n) to build each string

  • Space: O(n) recursion depth

Solution

java
1import java.util.*;
2
3class Solution {
4    private static final String[] PHONE = {
5        "",     // 0
6        "",     // 1
7        "abc",  // 2
8        "def",  // 3
9        "ghi",  // 4
10        "jkl",  // 5
11        "mno",  // 6
12        "pqrs", // 7
13        "tuv",  // 8
14        "wxyz"  // 9
15    };
16
17    public List<String> letterCombinations(String digits) {
18        List<String> result = new ArrayList<>();
19        if (digits == null || digits.length() == 0) {
20            return result;
21        }
22
23        backtrack(digits, 0, new StringBuilder(), result);
24        return result;
25    }
26
27    private void backtrack(String digits, int index, StringBuilder current, List<String> result) {
28        if (index == digits.length()) {
29            result.add(current.toString());
30            return;
31        }
32
33        String letters = PHONE[digits.charAt(index) - '0'];
34        for (char letter : letters.toCharArray()) {
35            current.append(letter);
36            backtrack(digits, index + 1, current, result);
37            current.deleteCharAt(current.length() - 1);
38        }
39    }
40}
41
Loading visualizer...