[알고리즘][그래프] - 2. 전화 번호 문자 조합

 

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다.

---

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

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

---

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