전화번호의 문자 조합

class Solution(object):
    def letterCombinations(self, digits):

        res = []
        if not digits:
            return res

        d = {
            "2":"abc", 
            "3": "def",
            "4":"ghi", 
            "5": "jkl", 
            "6":"mno", 
            "7": "pqrs", 
            "8":"tuv", 
            "9": "wxyz",    
        }

        def backtrack(i, curStr):
            if len(curStr) == len(digits):
                res.append(curStr)
                return

            for c in d[digits[i]]:
                backtrack(i + 1, curStr + c)


        backtrack(0, "")

        return res