## 1. Problem

17. Letter Combinations of a Phone Number

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.

**Example 1:**

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

**Example 2:**

```
Input: digits = ""
Output: []
```

**Example 3:**

```
Input: digits = "2"
Output: ["a","b","c"]
```

**Constraints:**

- 0 <= digits.length <= 4
- digits[i] is a digit in the range [‘2’, ‘9’].

## 2. Solution

I solved this problem like this.

```
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
dic = {
'2': "abc",
'3': "def",
'4': "ghi",
'5': "jkl",
'6': "mno",
'7': "pqrs",
'8': "tuv",
'9': "wxyz",
}
ans = []
def dfs(s, digit):
if len(digit) == 0:
ans.append(s)
return
for x in dic[digit[0]]:
dfs(s+x, digit[1:])
dfs('', digits)
return ans if digits else []
```