Every Letter Combination From a Phone Keypad Sequence
Solve this ProblemTest Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ digits.length ≤ 6 - ◆
digits[i] is one of '2'–'9', using the standard phone keypad letter mapping (2=abc, 3=def, 4=ghi, 5=jkl, 6=mno, 7=pqrs, 8=tuv, 9=wxyz) - ◆
An empty input returns an empty list of combinations - ◆
Results are returned sorted in ascending (lexicographic) order for a stable, checkable answer
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Rebuild the Whole Combination List at Every Digit
BruteKeep a running list of every combination built so far, starting with just the empty string. For each new digit, build a brand-new list by taking every existing combination and appending each of the new digit's letters to a copy of it, then replace the old list with this new one entirely. This produces the right answer, but every character from every previous digit gets copied again into a new string at every single step — the second digit alone rebuilds strings that already existed just to add one more character to each.
O(4ⁿ · n)O(4ⁿ · n)1class Solution {
2 public String[] keypadLetterCombinations(String digits) {
3 if (digits.length() == 0) return new String[0];
4 String[] keypad = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
5 List<String> combos = new ArrayList<>();
6 combos.add("");
7 for (char d : digits.toCharArray()) {
8 String letters = keypad[d - '0'];
9 List<String> next = new ArrayList<>();
10 for (String prefix : combos) {
11 for (char c : letters.toCharArray()) {
12 next.add(prefix + c);
13 }
14 }
15 combos = next;
16 }
17 Collections.sort(combos);
18 return combos.toArray(new String[0]);
19 }
20}Optimal — One Shared Buffer, Append and Pop
OptimalBuild one combination at a time using a single mutable buffer: at each digit position, append one of its letters, recurse into the next digit, then remove that letter again before trying the next one. Only the complete combinations that actually get recorded are ever turned into full strings — no intermediate list of partially-built combinations is created or copied at any point along the way.
O(4ⁿ · n)O(n)1class Solution {
2 private static final String[] KEYPAD = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
3
4 public String[] keypadLetterCombinations(String digits) {
5 List<String> result = new ArrayList<>();
6 if (digits.length() == 0) return new String[0];
7 StringBuilder path = new StringBuilder();
8 backtrack(digits, 0, path, result);
9 return result.toArray(new String[0]);
10 }
11
12 private void backtrack(String digits, int idx, StringBuilder path, List<String> result) {
13 if (idx == digits.length()) {
14 result.add(path.toString());
15 return;
16 }
17 String letters = KEYPAD[digits.charAt(idx) - '0'];
18 for (char c : letters.toCharArray()) {
19 path.append(c);
20 backtrack(digits, idx + 1, path, result);
21 path.deleteCharAt(path.length() - 1);
22 }
23 }
24}