Start learning free

LESSON 412 OF 678 · BACKTRACKING

Letter Combinations of a Phone Number

Practice O(n · 4n)

Given a string digits made of the digits 2 to 9, return every letter combination the number could spell on a phone keypad.

Each digit stands for the letters on its key:

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

A combination takes one letter from each digit's key, in the order of the digits. Return the combinations in keypad order: every combination that starts with the first letter of the first digit's key comes before every combination that starts with its second letter, and so on; inside each of those groups, the same rule for the second digit, then the third. (Each key's letters are in alphabetical order, so this is also alphabetical order.)

If digits is empty, there is nothing to spell: return no combinations at all, not one empty string.

 

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Explanation: 2 gives a, b or c, and 3 gives d, e or f: 3 × 3 = 9 combinations.
The three that start with a come first, in the order of 3's letters; then the ones that start with b, then c.

Example 2:

Input: digits = ""
Output: []
Explanation: No digits, so there are no combinations.

Example 3:

Input: digits = "7"
Output: ["p","q","r","s"]
Explanation: With one digit, each letter of its key is a combination. The keys 7 and 9 have four letters, the others three.

 

Constraints:

  • 0 <= digits.length <= 4
  • Each character of digits is a digit from '2' to '9'.

Note:

The tutorial uses backtracking. Walk through digits one position at a time, keeping the letters chosen so far in a string current. At position i, try each letter of the key of digits[i], in the key's order: add it to the end of current and go on to position i + 1. When the position reaches the end of digits, every digit has its letter: save current. Trying the letters in the key's order gives exactly the keypad order above. Each call gets its own longer string, so nothing has to be undone when a call returns.

Each key has at most 4 letters, so n digits give at most 4n combinations, and building one takes n steps: the time is O(n · 4n). Besides the answer, the search keeps at most O(n) calls open at a time, one per digit (their strings add up to O(n2) characters at most).

STEP 1 OF 11
    Ctrl + Enter to check