Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Map each digit to its letters.
  2. 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