Leetcode - Letter Combination of a Phone Number

Question

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Idea

• Actually a fairly simple Backtracking, the trick here is just understanding how backtracking functions
• This is a classic combinations question
• The solution space is the mapping from a digit to their potential letters
• Our state is represented the same way as it is in dp sort of, our current index, and our current result string
• The decision that we want to make is what letter to choose, we want to make sure we add this letter to a new variable as to not pollute our siblings and then call backtracking
• Our goal here is to explore all possible solutions, our end case is when our current string == len(digits)