17. Letter Combinations of a Phone Number.md

17. Letter Combinations of a Phone Number (Medium)

• tricky! do again later!
• levels (index) choose from digits('23'), so index will be +1 for next level, not letters.
• within each level, choose from letters 'abc', 'def'.

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        num_dict = defaultdict(list)
        offset = 0
        temp = []
        ans = []
        for i in range(2, 10):
            len_letter = 4 if (i == 7 or i == 9) else 3
            for j in range(len_letter):
                num_dict[i].append(chr(ord('a') + offset))
                offset += 1
        def dfs(index):
            if len(temp) == len(digits):
                temp_str = ''.join(temp)
                ans.append(temp_str)
                return
            for element in num_dict[int(digits[index])]:
                temp.append(element)
                dfs(index+1)
                temp.pop()
        
        dfs(0)
        return ans