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”].

Explanation: The answer is “abc”, with the length of 3.

**Note**:

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

## Solution

```
from typing import List
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
def helper(curString: List[str], i: int) -> None:
nonlocal digitLetterMap, combos
if i == len(digits):
combos.append("".join(curString))
return
for letter in digitLetterMap[int(digits[i])]:
curString[i] = letter
helper(curString, i+1)
if not digits: return []
digitLetterMap = ['0','1','abc','def','ghi','jkl','mno','pqrs','tuv','wxyz']
combos = []
helper([None]*len(digits), 0)
return combos
```

## Test Cases

```
test = Solution()
assert test.letterCombinations('23') == [
"ad",
"ae",
"af",
"bd",
"be",
"bf",
"cd",
"ce",
"cf"
]
assert test.letterCombinations('') == []
print('All Passed!')
```

## Big O Analysis

**Space Complexity**: O(4^{N})

**Time Complexity**: O(4^{N})