算法分析与设计课程（2）：Letter Combinations of a Phone Number

Description:

Given a digit string, return all possible letter combinations that the number could rePResent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].算法思路：这种情况下很容易想到用递归的方法。
                   将字串的第一个字符和其他字符看成两个部分，用第一个字符产生字符串，连接上其余部分的字符串，即可枚举所有的组合
代码如下：
__author__ = 'andy'class Solution(object):    def letterCombinations(self, digits):        dicLetter = {0:' ',1:'',2:'abc',3:'def',4:'ghi',5:'jkl',6:'mno',7:'pqrs',8:'tuv',9:'wxyz'}        length = len(digits)        if length == 0:            return []        intIndex = int(digits[0])        result = []        arr = []        #第一个字符        letter = dicLetter[intIndex]        for l in letter:            if length > 1:                #其他的字符                arr =self.letterCombinations(digits[1:])                for m in arr:                    result.append(l+m)            else:                result.append(l)        return resultcase = Solution()print(case.letterCombinations("23"))
运行结果如下图：