17.py

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        
        dic = {
            "2" : ["a","b","c"],
            "3" : ["d","e","f"],
            "4" : ["g", "h", "i"],
            "5" : ["j","k","l"],
            "6" : ["m", "n", "o"],
            "7" : ["p", "q", "r", "s"],
            "8" : ["t", "u", "v"],
            "9" : ["w","x","y","z"]
        }
        
        
        result = []
        def dfs(digits: str, stack: star) -> List[str]:
            if not digits:
                result.append(stack)
                return
                
            for char in dic[digits[0]]:
                dfs(digits[1:], stack + char)
                    
            return result
            
            
            
        return dfs(digits, "")