Old phones had letters on the number keys. You are given a string digits made of the digits 2 to 9. Imagine pressing these keys. Return every letter string that the key presses could mean. Return the answer in any order.
Letters on the keys:
- 2 = abc
- 3 = def
- 4 = ghi
- 5 = jkl
- 6 = mno
- 7 = pqrs
- 8 = tuv
- 9 = wxyz
The key 1 has no letters.
Examples
Example 1:
Input: digits = "45"
Output: ["gj","gk","gl","hj","hk","hl","ij","ik","il"]
Explanation: The first letter is g, h or i. The second letter is j, k or l. That gives 3 x 3 = 9 strings.
Example 2:
Input: digits = "29"
Output: ["aw","ax","ay","az","bw","bx","by","bz","cw","cx","cy","cz"]
Explanation: The first letter is a, b or c. The second letter is w, x, y or z. That gives 3 x 4 = 12 strings.
Example 3:
Input: digits = ""
Output: []
Explanation: No key was pressed, so the list is empty.