# Problem

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

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

Example:

Input: "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

# Thought Process

The problem can be structured as a tree, as shown in below

# White Board

Below is the white board:

# Code

class Solution:

def _findcombo(self, digits, idx, s):
# s stores the string of digits[0, idx-1]
# find the letter corresponding to digits[idx], then got the solution of digits[0,idx]
letter_map = {
2: "abc",
3: "cdf",
4: "ghi",
5: "jkl",
6: "mno",
7: "pqrs",
8: "tuv",
9: "wxyz"
}

def letterCombinations(self, digits: str) -> List[str]:
pass


# Complexity

• Time complexity is O(n)

# Optimization

Maybe have an iterative solution...