class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        m = {
            1: '',
            2: 'abc',
            3: 'def',
            4: 'ghi',
            5: 'jkl',
            6: 'mno',
            7: 'pqrs',
            8: 'tuv',
            9: 'wxyz',
        }
        rlt = []
        for ch in digits:
            num = int(ch)
            if len(rlt) == 0:
                for l in m[num]:
                    rlt.append(l)
            else:
                tmp_rlt = rlt.copy()
                for length in range(len(m[num])):
                    ch = m[num][length]
                    if length == 0:
                        for index, s in enumerate(rlt):
                            rlt[index] = tmp_rlt[index] + ch
                    else:
                        for index, s in enumerate(tmp_rlt):
                            rlt.append(tmp_rlt[index] + ch)                            
        return rlt