[Leetcode] 리트코드 - 전화 번호 문자 조합(letter-combinations-of-a-phone-number) 파이썬(python) 풀이

전화 번호 문자 조합

문제

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

입력 : "23"
출력 : ["ad","ae","af","bd","be","bf","cd","ce","cf"]

코드

from typing import List

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

Solution().letterCombinations("23")

풀이

전체를 탐색한 후 백트래킹을 하는 형태로 구현.

if len(path) == len(digits):
    result.append(path)
    return

지금까지 붙여온 path 문자열의 길이와 digits의 길이가 같다면 즉, 탐색이 끝났으면 결과에 추가시킨뒤에 내부 함수를 종료 시킨다.

for i in range(index, len(digits)):
    for j in dic[digits[i]]:
        dfs(i + 1, path + j)

i, j 및 dfs 함수를 순서대로 따라가면 이런식으로 백트래킹 됨을 알 수 있다.

i : 0, j: a, dfs(1, a)
i : 1, j: d, dfs(2, ad)
['ad']
return

i : 1, j: e, dfs(2, ae)
['ad', 'ae']
return

i : 1, j: f, dfs(2, af)
['ad', 'ae', 'af']
return

i : 0, j: b, dfs(1, b)
i : 1, j: d, dfs(2, bd)
['ad', 'ae', 'af', 'bd']
return

i : 1, j: e, dfs(2, be)
['ad', 'ae', 'af', 'bd', 'be']
return

i : 1, j: f, dfs(2, bf)
['ad', 'ae', 'af', 'bd', 'be', 'bf']
return

i : 0, j: c, dfs(1, c)
i : 1, j: d, dfs(2, cd)
['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd']
return

i : 1, j: e, dfs(2, ce)
['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce']
return

i : 1, j: f, dfs(2, cf)
['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
return

i : 1, j: d, dfs(2, d)
i : 1, j: e, dfs(2, e)
i : 1, j: f, dfs(2, f)

헷갈렸던 점

맨 처음 i가 0일 때의 모든 재귀가 끝나고 i가 1일 때 즉, 위 쪽 결과에서 맨밑 3줄에 해당하는 지점에서는 dfs가 호출되고 range(2, 2)(현재의 예제에서는)와 같이 for문의 범위에 해당하는 값이 없어서 아무것도 수행되지 않고 끝나게 된다.

출처

파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]