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