Letter Combinations of a Phone Number

Problem

Given a string of digits 2-9, return all possible letter combinations they could spell on a classic phone keypad (2=abc, 3=def, …, 9=wxyz). Order doesn't matter.

Constraints

• 0 ≤ digits.length ≤ 4
• digits are 2-9

Approach — Backtracking

This is a Backtracking problem. The idea: build candidates one choice at a time and abandon a branch the moment it can't lead to a valid answer. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: exponential worst case.

Solution code

Python

class Solution:
    def letterCombinations(self, digits):
        if not digits:
            return []
        m = {'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
        res = ['']
        for d in digits:
            res = [p + ch for p in res for ch in m[d]]
        return res

Java

import java.util.*;

class Solution {
    private static final String[] LETTERS = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

    public List<String> letterCombinations(String digits) {
        List<String> out = new ArrayList<>();
        if (digits.isEmpty()) return out;
        bt(out, new StringBuilder(), digits, 0);
        return out;
    }

    private void bt(List<String> out, StringBuilder cur, String digits, int i) {
        if (i == digits.length()) { out.add(cur.toString()); return; }
        for (char c : LETTERS[digits.charAt(i) - '0'].toCharArray()) {
            cur.append(c);
            bt(out, cur, digits, i + 1);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.