[파이썬 알고리즘 인터뷰] 17. 전화번호 문자 조합

1. 문제

leetcode 17. letter combinations of a phone number

2에서 9까지 숫자가 주어졌을 때 전화번호로 조합 가능한 모든 문자를 출력하라. 숫자와 문자의 관계는 다음과 같다.

 

 

2. DFS를 이용한 해결 방법

이 문제는 하나의 경로로 탐색을 시작하면 해당 경로로 탐색을 마쳐야 한다. 따라서 DFS(깊이 우선 탐색)를 사용해야 한다. 

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

 문제를 풀 때는 숫자를 key, 숫자와 매칭된 문자들을 value로 하는 딕셔너리를 만들어서 활용한다. 재귀함수는 주어진 숫자의 길이만큼 반복하고, 해당 숫자와 매칭된 문자의 개수만큼 반복하며 재귀 호출을 한다. 그러다 문자열의 탐색을 완료했다면 호출을 종료한다. 호출에 사용되는 인자는 주어진 숫자 중 몇 번째 숫자에 해당하는 문자열을 찾아야 하는지 알려주는 index, 지금까지 만들어진 문자열을 저장하는 path 두 가지가 있다.