Letter Combinations of a Phone Number
MediumBacktracking
Each digit from 2 to 9 on a phone keypad stands for a few letters:
| Digit | Letters |
|---|---|
| 2 | abc |
| 3 | def |
| 4 | ghi |
| 5 | jkl |
| 6 | mno |
| 7 | pqrs |
| 8 | tuv |
| 9 | wxyz |
Given a string digits, return every string you can form by picking one letter for each digit, keeping the letters in the same order as the digits. The returned list may be in any order. If digits is empty, return an empty list.
Example 1
- Input:
- digits = "79"
- Output:
- ["pw","px","py","pz","qw","qx","qy","qz","rw","rx","ry","rz","sw","sx","sy","sz"]
- Explanation
- 7 maps to p, q, r, s and 9 maps to w, x, y, z. Each of the 4 choices for the first letter pairs with each of the 4 for the second, giving 4 x 4 = 16 strings.
Example 2
- Input:
- digits = "38"
- Output:
- ["dt","du","dv","et","eu","ev","ft","fu","fv"]
- Explanation
- 3 gives d, e, f and 8 gives t, u, v, so there are 3 x 3 = 9 two-letter strings. The first letter always comes from 3 because 3 is first in
digits.
Example 3
- Input:
- digits = "7"
- Output:
- ["p","q","r","s"]
- Explanation
- A single digit simply yields each of its letters.
Constraints
0 <= digits.length <= 4digits[i]is a character from"2"to"9"