class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if digits == "":
            return []
        def DFS(res, s, aa, i):
            if i >= len(aa):
                # print("i:", i, "res:", res, "s:", s)
                return res.append(s)
            for item in aa[i]:
                DFS(res, s+item, aa, i+1)
                
        s = digits
        n = len(s)
        chars = [[],[],["abc"],["def"], ["ghi"],["jkl"],["mno"],["pqrs"],["tuv"],["wxyz"]]
        dChars = []
        for c in s:
            d = int(c)
            # print("sss:", [c for c in chars[d][0]])
            dChars.append([c for c in chars[d][0]])
        # print(dChars)
        if len(dChars) == 1:
            return dChars[0]
        res = []
        for item in dChars[0]:
            s = item
            DFS(res, s, dChars,1)
        return res