All problems

Letter Combinations of a Phone Number

Medium · backtracking

On an old mobile phone keypad, each digit from 2 to 9 is printed with some letters:

| Digit | Letters | | --- | --- | | 2 | a b c | | 3 | d e f | | 4 | g h i | | 5 | j k l | | 6 | m n o | | 7 | p q r s | | 8 | t u v | | 9 | w x y z |

You are given a text digits made only of the characters 2 to 9. Someone pressed those keys in that order, once each, and for every key they meant any one of its letters.

Return every word of letters they could have meant, in alphabetical (dictionary) order. Each word has exactly one letter per digit. If digits is empty, return an empty list.

Examples

Example 1

Input: digits = "23"

Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

The first key gives a, b or c and the second gives d, e or f, so there are 3 * 3 = 9 words.

Example 2

Input: digits = "7"

Output: ["p", "q", "r", "s"]

The key 7 has four letters.

Example 3

Input: digits = ""

Output: []

No keys were pressed, so there are no words.

Constraints