Recursion and Backtracking Generating every choice
323. Letter Combinations of a Phone Number
You are given a string digits. Each character is a digit from 2 to 9, and each of these digits sits on a
phone key that carries three or four letters:
2 abc 3 def 4 ghi 5 jkl
6 mno 7 pqrs 8 tuv 9 wxyz
Return every string that has one letter for each digit, in the same order as the digits, where each letter is
one of the letters on its digit's key. If digits is empty, return an empty list, [].
The strings can come in any order.
Example 1
Input: digits = "47"
["gp",
"gq",
"gr",
"gs",
"hp",
"hq",
"hr",
"hs",
"ip",
"iq",
"ir",
"is"]Explanation: Key 4 has three letters and key 7 has four, so there are 3 × 4 = 12 strings. Each one starts with g,
h or i and ends with p, q, r or s.
Example 2
Input: digits = "33"
["dd","de","df","ed","ee","ef","fd","fe","ff"]Explanation: Each copy of the digit picks its own letter, so dd and ff count. That makes 3 × 3 = 9 strings.
Example 3
Input: digits = ""
[]Explanation: With no digits there is nothing to build. The answer is an empty list, not a list that holds the empty string.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
0 ≤ digits.length ≤ 8- Every character of
digitsis a digit from2to9.
Clarifying questions
What you would ask an interviewer before writing any code.