# [leetcode] 17. Letter Combinations of a Phone Number _ Algorithm Problem Solve for python

## 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 []