614. Keypad Words
An old mobile phone keypad maps digits to letters: 2 to abc, 3 to def, 4 to ghi, 5 to jkl, 6 to mno, 7 to pqrs, 8 to tuv and 9 to wxyz. Pressing each digit once, in order, lets the user type any string that takes one letter from each pressed key.
Given the string digits, return every string that could be typed. Each string appears once and may be returned in any order. If digits is empty, return an empty array.
Example 1
- Input:
- digits = "57"
- Output:
- ["jp","jq","jr","js","kp","kq","kr","ks","lp","lq","lr","ls"]
- Explanation:
Key 5 offers j, k, l and key 7 offers p, q, r, s, so there are 3 * 4 = 12 strings such as
jpandls.
Example 2
- Input:
- digits = ""
- Output:
- []
- Explanation:
No key was pressed, so nothing can be typed and the answer is empty.
Example 3
- Input:
- digits = "8"
- Output:
- ["t","u","v"]
- Explanation:
A single key gives its own letters:
t,u,v.
Constraints
- 0 ≤
digits.length≤ 4 - Each character of
digitsis a digit from2to9.
How this problem is judged
- Answers
- The outer list may be in any order. Everything inside each item must match exactly.
Expected complexity
- Time
- O(4^n * n)
- Space
- O(n)