Letter Combinations of a Phone Number
Letter Combinations of a Phone Number is a medium recursion & backtracking problem solved with the choice per position pattern.
The best approach, optimal (backtracking with one shared buffer), runs in O(4^n · n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from iterative expansion up.
Problem
On an old phone keypad, each digit from 2 to 9 sits on a key printed with a few letters: 2 → abc, 3 → def, 4 → ghi, 5 → jkl, 6 → mno, 7 → pqrs, 8 → tuv, 9 → wxyz.
Given a string digits, return every word you could type by choosing one letter from each digit’s key, keeping the digits’ order. The words may be returned in any order. An empty input gives an empty list.
Examples
Example 1
- Input
digits = "53"- Output
["jd", "je", "jf", "kd", "ke", "kf", "ld", "le", "lf"]- Why
- 5 maps to j, k, l and 3 maps to d, e, f, so there are 3 × 3 = 9 words.
Example 2
- Input
digits = "7"- Output
["p", "q", "r", "s"]- Why
- A single digit gives one word per letter on its key.
Example 3
- Input
digits = ""- Output
[]- Why
- No digits means no words at all, not one empty word.
Constraints
0 <= digits.length <= 4- Each
digits[i]is a digit from'2'to'9'.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Iterative expansion | O(4^n · n) | O(4^n · n) |
| Optimal (backtracking with one shared buffer) | O(4^n · n) | O(n) |
1Iterative expansion
O(4^n · n)There are up to 4^n words and each one is built by copying a string of length up to n.O(4^n · n)The current and next lists together hold all words of the current length.Start with a list holding the empty word. For each digit, replace the list by every old word extended with every letter of that digit.
- If digits is empty, return an empty list.
- words = [""].
- For each digit d: next = []; for each w in words, for each letter c of d, add w + c to next; words = next.
- Return words.
class Solution {
private static final String[] KEYS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public List<String> letterCombinations(String digits) {
List<String> words = new ArrayList<>();
if (digits.isEmpty()) return words;
words.add("");
for (char d : digits.toCharArray()) {
List<String> next = new ArrayList<>();
for (String w : words) {
for (char c : KEYS[d - '0'].toCharArray()) {
next.add(w + c);
}
}
words = next;
}
return words;
}
}class Solution:
KEYS = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
words = [""]
for d in digits:
nxt = []
for w in words:
for c in self.KEYS[int(d)]:
nxt.append(w + c)
words = nxt
return wordsclass Solution {
const vector<string> KEYS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public:
vector<string> letterCombinations(string digits) {
vector<string> words;
if (digits.empty()) return words;
words.push_back("");
for (char d : digits) {
vector<string> next;
for (const string& w : words) {
for (char c : KEYS[d - '0']) {
next.push_back(w + c);
}
}
words = next;
}
return words;
}
};function letterCombinations(digits) {
const KEYS = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
if (digits.length === 0) return [];
let words = [""];
for (const d of digits) {
const next = [];
for (const w of words) {
for (const c of KEYS[Number(d)]) {
next.push(w + c);
}
}
words = next;
}
return words;
}2Optimal (backtracking with one shared buffer)
O(4^n · n)Up to 4^n leaves, and turning each finished buffer into a string costs n.O(n)The buffer and the recursion depth are both n (not counting the output).Fill a character buffer one position at a time. At position i try every letter of digits[i] and recurse to position i + 1; when the buffer is full, record it as a word. Each letter is written once per branch, and only finished words are turned into strings.
- If digits is empty, return an empty list.
- build(i): if i == n, add the buffer as a string and return.
- Otherwise, for each letter c of digits[i]: buf[i] = c; build(i + 1).
- Call build(0) and return the result.
class Solution {
private static final String[] KEYS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public List<String> letterCombinations(String digits) {
List<String> out = new ArrayList<>();
if (digits.isEmpty()) return out;
build(digits, 0, new char[digits.length()], out);
return out;
}
private void build(String digits, int i, char[] buf, List<String> out) {
if (i == digits.length()) {
out.add(new String(buf));
return;
}
for (char c : KEYS[digits.charAt(i) - '0'].toCharArray()) {
buf[i] = c;
build(digits, i + 1, buf, out);
}
}
}class Solution:
KEYS = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
def letterCombinations(self, digits: str) -> List[str]:
out = []
if not digits:
return out
buf = [""] * len(digits)
def build(i: int) -> None:
if i == len(digits):
out.append("".join(buf))
return
for c in self.KEYS[int(digits[i])]:
buf[i] = c
build(i + 1)
build(0)
return outclass Solution {
const vector<string> KEYS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
void build(const string& digits, int i, string& buf, vector<string>& out) {
if (i == (int) digits.size()) {
out.push_back(buf);
return;
}
for (char c : KEYS[digits[i] - '0']) {
buf[i] = c;
build(digits, i + 1, buf, out);
}
}
public:
vector<string> letterCombinations(string digits) {
vector<string> out;
if (digits.empty()) return out;
string buf(digits.size(), ' ');
build(digits, 0, buf, out);
return out;
}
};function letterCombinations(digits) {
const KEYS = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
const out = [];
if (digits.length === 0) return out;
const buf = new Array(digits.length);
const build = (i) => {
if (i === digits.length) {
out.push(buf.join(""));
return;
}
for (const c of KEYS[Number(digits[i])]) {
buf[i] = c;
build(i + 1);
}
};
build(0);
return out;
}Edge cases to test
- An empty string returns an empty list
- Keys 7 and 9 carry four letters, the others three
- Repeated digits like "22" still produce every pair, including "aa"
Hints
Hint 1
The answer is every way to pick one letter for each position. How many words are there for n digits?
Hint 2
Build the words position by position: for the first digit try each of its letters, then recurse on the rest.
Hint 3
Keep one shared character buffer; write a letter, recurse, and simply overwrite it with the next letter (no copying of partial strings).
FAQ
What is the best time complexity for Letter Combinations of a Phone Number?
Optimal (backtracking with one shared buffer) runs in O(4^n · n) time and O(n) extra space. Up to 4^n leaves, and turning each finished buffer into a string costs n.
Which pattern does Letter Combinations of a Phone Number use?
It is a recursion & backtracking problem that uses the choice per position pattern. Other problems with the same pattern: Confusing Number II, Strobogrammatic Number II, Palindrome Partitioning.
Is there a brute force solution for Letter Combinations of a Phone Number?
Yes. Iterative expansion takes O(4^n · n) time and O(4^n · n) space. Start with a list holding the empty word.
Which edge cases should I test for Letter Combinations of a Phone Number?
An empty string returns an empty list; Keys 7 and 9 carry four letters, the others three; Repeated digits like "22" still produce every pair, including "aa".