def letterCombinations(self, digits: str) -> List[str]:
def dfs(index, path):
if len(path) == len(digits):
result.append(path)
return
for i in range(index, len(digits)): # i가 커지면 한 줄씩 내려가는거
for j in dic[digits[i]]: # j가 커지면 알파벳이 바뀌는 거
dfs(i + 1, path + j)
if not digits:
return []
dic = {"2": "abc", "3" : "def", "4" : "ghi", "5": "jkl",
"6" : "mno", "7" : "pqrs", "8" : "tuv", "9" : "wxyz"}
result = ""
def(0, "")
return result