Medium
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: []
나의 코드
class Solution(object):
res = [] # list of results
letter = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
self.res = [] # 결과 배열 초기화
if digits == "": return []
self.dfs(digits, 0, []) # DFS
return self.res
def dfs(self, d1, cnt, d2):
"""
:param d1: str 탐색하려는 번호
:param cnt: int 길이
:param d2: List[char] 찾은 letters
"""
if len(d1) == cnt:
self.res.append("".join(d2)) # add to list res
else:
idx = int(d1[cnt]) # 탐색할 number에서 letter를 찾을 index
for j in range(len(self.letter[idx])): # letter
d2.append(self.letter[idx][j]) # add a letter to d2
self.dfs(d1, cnt + 1, d2) # DFS
del d2[len(d2) - 1] # 추가했던 letter를 삭제
