Letter Combinations of a Phone Number

NeetCode: Letter Combinations of a Phone Number · LeetCode: 17. Letter Combinations of a Phone Number · Difficulty: Medium

Given a string digits containing digits from 2 to 9, return all letter combinations it could represent on a classic phone keypad (2 = abc, 3 = def, 4 = ghi, 5 = jkl, 6 = mno, 7 = pqrs, 8 = tuv, 9 = wxyz). Return an empty list for an empty input.

Example

Text

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

Brute force: expand all prefixes digit by digit

The keypad is a String[] indexed by the digit, so KEYS[d - '0'] gives the letters of digit d (char arithmetic turns '7' into the int 7). Start with one empty string. For each digit, replace every string built so far with one copy per letter of that digit. After the last digit you hold every combination. No work is wasted, but every intermediate string is allocated and copied, and the whole previous level is kept in memory at once.

Java

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

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

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

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

Output

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

Time: O(n · 4^n) (at most 4 letters per digit, strings up to length n). Space: O(4^n) extra for the intermediate level, on top of the result.

Optimal: backtracking with one buffer

The output size O(n · 4^n) is a lower bound, so the complexity is the same as before, with less intermediate allocation. Recurse over the digit positions: at each one append a letter to a single StringBuilder buffer, recurse, and remove it with deleteCharAt. Only complete strings are copied, and the recursion depth is n.

Java

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

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

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

        private void dfs(int i, String digits, StringBuilder buf, List<String> result) {
            if (i == digits.length()) {
                result.add(buf.toString());
                return;
            }
            for (char ch : KEYS[digits.charAt(i) - '0'].toCharArray()) {
                buf.append(ch);
                dfs(i + 1, digits, buf, result);
                buf.deleteCharAt(buf.length() - 1);
            }
        }
    }

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

Output

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

Time: O(n · 4^n). Space: O(n) besides the output.