电话号码的组合

#encoding=utf-8
'''
给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合
输入："23"
输出：['ad', 'bd', 'cd', 'ae', 'be', 'ce', 'af', 'bf', 'cf']
'''
class Solution(object):
    def letterCombination(self,digits):
        '''
        :param digits: str
        :return: List[str]
        '''
        dic = {
            2:['a','b','c'],
            3:['d','e','f'],
            4:['g','h','i'],
            5:['j','k','l'],
            6:['m','n','0'],
            7:['p','q','r','s'],
            8:['t','u','v'],
            9:['w','x','y','z']
        }
        ret_str = []
        if len(digits)==0:
            return []
        if len(digits)==1:
            return dic[int(digits[0])]
        result = self.letterCombination(digits[1:])
        for r in result:
            for j in dic[int(digits[0])]:
                ret_str.append(j+r)
        return ret_str
if __name__ == "__main__":
    s = Solution()
    print (s.letterCombination("23"))