[leetcode] 17. Letter Combinations of a Phone Number 파이썬 코드

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

 

각 숫자마다 designated letter들이 있다.

digits가 "23"일 때 2에 있는 문자 a, b, c와 3에 있는 문자 d, e, f의 조합으로 몇 개의 letter combination을 만들 수 있는지 구하는 문제다.

 

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        res = []
        digitsToChar = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz"
        }

        def dfs(i, currStr):
            if i == len(digits):
                res.append(currStr)
                return True

            for c in digitsToChar[digits[i]]:
                dfs(i+1, currStr+c)

        if digits:
            dfs(0, "")
        return res