LeetCode#17. Letter Combinations

电话键盘上有9个数字，其中2~9分别代表了几个字母，如2:ABC，3:DEF......等等。给定一个数字序列，输出它所对应的所有字母序列。
看了答案，又看了半天回溯算法之后，半懂不懂的提交了代码，竟然通过了。。。。一脸蒙蔽

class Solution(object):
    def letterCombinations(self, digits):
#用字典保存对应关系
        dic = {
            '2':'abc',
            '3':'def',
            '4':'ghi',
            '5':'jkl',
            '6':'mno',
            '7':'pqrs',
            '8':'tuv',
            '9':'wxyz'
        }
        if len(digits) ==0:
            return []
        elif len(digits) == 1:
            return list(dic[digits])
        else:
            digit = digits[0]
#递归到最后一个数字
            resu = self.letterCombinations(digits[1:])
            new = []
            for i in dic[digit]:
                if len(resu) == 0:
                    new.append(i)
                else:
                    for j in range(len(resu)):
                        new.append(i+resu[j])
            return new