Letter Combinations of a Phone Number
Generate the letter combinations of a phone keypad: 2=abc, 3=def, 4=ghi, 5=jkl, 6=mno, 7=pqrs, 8=tuv, 9=wxyz.
Work through the cases
3 examplesInput notation
A string of 1 to 4 digits from 2 through 9.Expected result
Combinations in alphabetical order, separated by spaces.Case 1
Input
23
Expected output
ad ae af bd be bf cd ce cf
Case 2
Input
7
Expected output
p q r s
Case 3
Input
2
Expected output
a b c
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
n ≤ 4, so at most 4^n combinations; any enumeration would pass. The problem is a Cartesian product of letter groups. Nested loops cannot be written when n is not fixed. Start from the empty string: each new digit replaces the current prefixes with every concatenation against that digit’s letters. That is the product expanded layer by layer. So we keep a mapping array and grow from a list that holds only the empty string. An empty input returns an empty list.
First, we use an array or hash table to store the letters corresponding to each digit. Then we traverse each digit, combine its corresponding letters with the previous results to get the new results.
The time complexity is O(4^n), and the space complexity is O(4^n). Here, n is the length of the input digits.
class Solution {
public List<String> letterCombinations(String digits) {
List<String> ans = new ArrayList<>();
if (digits.length() == 0) {
return ans;
}
ans.add("");
String[] d = new String[] {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
for (char i : digits.toCharArray()) {
String s = d[i - '2'];
List<String> t = new ArrayList<>();
for (String a : ans) {
for (String b : s.split("")) {
t.add(a + b);
}
}
ans = t;
}
return ans;
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.