17. Letter Combinations of a Phone Number

class Solution:
    def letterCombinations(self, digits):
        def dfs(index, cur):
            # 문자의 길이가 숫자의 길이랑 같아지면 다 찾은거임
            if len(cur) == len(digits):
                output.append(cur)
                return

            # i로 숫자 선택하고
            for i in range(index, len(digits)):
                # j로 i가 가진 문자 선택해서 현재 문자열에 문자 추가해줌
                for j in dic[digits[i]]:
                    dfs(i + 1, cur + j)


        # 입력이 string으로 와서 키를 스트링으로 만들어야함
        dic = {'2': 'abc', '3': 'def', '4': 'ghi',
               '5': 'jkl', '6': 'mno', '7': 'pqrs',
               '8': 'tuv', '9': 'wxyz'}

        # 빈 문자열오면 []리턴해야함
        if digits == "":
            return []
        
        output = []
        dfs(0, "")

        return output

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