Practice › Recursion & Backtracking
Letter Combinations of a Phone Number
Medium · Recursion & Backtracking · Asked at Amazon, Google, Meta, Microsoft, Uber
On a phone keypad 2 = abc, 3 = def, 4 = ghi, 5 = jkl, 6 = mno, 7 = pqrs, 8 = tuv, 9 = wxyz. Print every letter combination the digit string could represent, in lexicographic order, one per line.
Input
A single string of digits from 2 to 9.
Output
The combinations, one per line.
Constraints
- 1 ≤ length ≤ 6
Recursion: for the current digit, try each of its letters and recurse on the rest of the digits.
Example 1
Input
23
Output
ad ae af bd be bf cd ce cf
Example 2
Input
7
Output
p q r s
Hints
- Map each digit to its letters.
- Recurse over the digits: for the current digit, try each of its letters in order and continue with the next digit.
Approach
go(i, cur): if i equals the number of digits, output cur. Otherwise for every letter of keys[digits[i]] (already in alphabetical order) recurse with i + 1. Since earlier positions vary slowest, the combinations come out in lexicographic order. There are at most 4^6 = 4096 of them.
Complexity: O(4^n · n) time · O(n) recursion depth
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
string keys[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
string digits, out;
void go(size_t i, string &cur) {
if (i == digits.size()) {
out += cur + "\n";
return;
}
for (char c : keys[digits[i] - '0']) {
cur.push_back(c);
go(i + 1, cur);
cur.pop_back();
}
}
int main() {
cin >> digits;
string cur;
go(0, cur);
cout << out;
return 0;
}Python solution
keys = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
digits = input().strip()
out = []
def go(i, cur):
if i == len(digits):
out.append(cur)
return
for c in keys[digits[i]]:
go(i + 1, cur + c)
go(0, "")
print("\n".join(out))Java solution
import java.util.*;
public class Main {
static String[] keys = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
static String digits;
static StringBuilder out = new StringBuilder();
static void go(int i, String cur) {
if (i == digits.length()) {
out.append(cur).append('\n');
return;
}
for (char c : keys[digits.charAt(i) - '0'].toCharArray()) go(i + 1, cur + c);
}
public static void main(String[] args) {
digits = new Scanner(System.in).next();
go(0, "");
System.out.print(out);
}
}Solve Letter Combinations of a Phone Number online · All practice problems