[LeetCode/Python] 17. Letter Combinations of a Phone Number

2에서 9까지 숫자가 주어졌을 때 전화번호로 조합 가능한 모든 문자를 출력하라.

 

 

 

Example:

 

Input: digits = "23"

Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

 

 

 

 

꼭 재귀를 return으로만 구성할 필요는 없다.

 

특히 이번 문제는 for문을 이용해서 조합하는 문제인데

 

return을 쓰면 중간에 return 때문에 끊긴다.

 

 

 

** 깔끔한 답안 **

 

1. 모든 조합 탐색

 

 

class Solution:
    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)):
                # 숫자에 해당하는 모든 문자열 반복
                for j in dic[digits[i]]:
                    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 = []
        dfs(0,"")
        
        return result

 

 

해설:

 

path를 이용하여 문자를 조합해 나간다.

 

path의 길이와 digits의 길이가 같으면

 

조합이 완료된 것이니까 result에 추가하고 리턴한다.