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

 

 이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다.

 

 출처 : 파이썬 알고리즘 인터뷰

 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브

 

---

33. 전화 번호 문자 조합

leetcode 17. Letter Combinations of a Phone Number 문제입니다.

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

 

 

풀이

def letterCombinations(self, digits):
    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