[LeetCode] #17. Letter Combinations of a Phone Number (python)

문제

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

Letter Combinations of a Phone Number - LeetCode

숫자 2-9는 각각 의미하는 문자들이 있는데 해당 번호로 가능한 모든 문자들의 조합을 반환해야 한다.

 

예시 입출력

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

 

 

 

풀이

 

책 풀이

 

전체 탐색

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

우선 숫자에 해당하는 문자들을 딕셔너리로 만든다. 키 값은 숫자, 값은 가능한 문자들을 하나의 문자열로 합친 것이다.

주어진 숫자를 차례대로 탐색한다. 그 숫자에 해당하는 문자들을 재귀호출을 통해 모두 탐색한다. 끝까지 탐색하면 최종 결과에 값을 추가한다.

 

참고한 책 : 파이썬 알고리즘 인터뷰