[Python] Leetcode 17. Letter Combinations of a Phone Number
Leetcode 17. Letter Combinations of a Phone Number
1. 문제
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.
설명
- 백트래킹을 통해 모든 가능한 경우의 수를 탐색하기
풀이
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
my_dict = {'2': ['a', 'b', 'c'],
'3': ['d', 'e', 'f'],
'4': ['g', 'h', 'i'],
'5': ['j', 'k', 'l'],
'6': ['m', 'n', 'o'],
'7': ['p', 'q', 'r', 's'],
'8': ['t', 'u', 'v'],
'9': ['w', 'x', 'y', 'z']}
res = []
digits_list = list(digits)
def dfs(depth, answer):
if depth==len(digits_list):
res.append(''.join(answer))
return
num = digits_list[depth]
for i in range(len(my_dict[num])):
dfs(depth+1, answer+[my_dict[num][i]])
dfs(0, [])
return res
