Letter Combinations of a Phone Number

Given a string of digits from 2 to 9, return all the letter combinations they could represent on a phone keypad.

Text

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

LeetCode: 17. Letter Combinations of a Phone Number

Example

Text

"23"  ->  ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
""    ->  []

Extend all partial strings, digit by digit

Start with one empty string. For each digit, replace every partial string with one copy per letter of that digit.

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static final String[] KEYS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    static List<String> letterCombinations(String digits) {
        List<String> partial = new ArrayList<>();
        if (digits.isEmpty()) return partial;
        partial.add("");
        for (char d : digits.toCharArray()) {
            String letters = KEYS[d - '0'];
            List<String> next = new ArrayList<>();
            for (String prefix : partial) {
                for (char c : letters.toCharArray()) next.add(prefix + c);
            }
            partial = next;
        }
        return partial;
    }

    public static void main(String[] args) {
        System.out.println(letterCombinations("23"));
    }
}

Output

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

List.toString prints strings without quotes.

Time: O(4ⁿ · n) for n digits: up to 4ⁿ results, each of length n. Space: O(4ⁿ · n), and every level allocates a whole new list of partial strings.

Backtracking: one string at a time

Build a single string depth-first. At depth i, try each letter of digits[i], recurse, then remove the letter. A string is copied (toString()) only when it's complete. digits.charAt(i) - '0' turns a digit character into its numeric value, because char arithmetic works on character codes.

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static final String[] KEYS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

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

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

    public static void main(String[] args) {
        System.out.println(letterCombinations("23"));
        System.out.println(letterCombinations("") + " " + letterCombinations("79").size());
        System.out.println(letterCombinations("21"));
    }
}

Output

[ad, ae, af, bd, be, bf, cd, ce, cf]
[] 16
[]

Time: O(4ⁿ · n), which is the size of the output, so it can't be improved. Space: O(n) for the recursion and the current string, besides the output.

Edge cases

Empty input: an empty list, not a list containing one empty string. Both versions check this explicitly.
Digits 0 and 1: have no letters. With KEYS mapping them to "" (the last call shows "21"), any input containing them produces no combinations.