Problem Definition:

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"].

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

 

Solution:

1）遍历。遍历每一个数字，找到它可能指向的字符，把每一个字符与前面已经形成的串拼接。

例如输入数字串为'23'。

  　　1._数字为'2'，可能的串为['a', 'b', 'c']

  　　2._数字为'3', 对应的字符为['d', 'e', 'f']，分别与1._中形成的所有串拼接，得到：['ad','ae','af',    'bd','be','bf',    'cd','ce','cf'].

1     # @param {string} digits 2     # @return {string[]} 3     def letterCombinations(digits): 4         if digits=='': 5             return [] 6         dic={
   '2':['a','b','c'],'3':['d','e','f'],'4':['g','h','i'],'5':['j','k','l'], 7              '6':['m','n','o'],'7':['p','q','r','s'],'8':['t','u','v'],'9':['w','x','y','z']} 8         cmb=[''] 9         for d in digits:10             chs=dic[d]11             res=[]12             for pre in cmb:13                 for sub in chs:14                     res+=(pre+sub)15             cmb=res16         return cmb

 

2）以上过程用Python实现，可以利用reduce函数：

1     # @param {string} digits2     # @return {string[]}3     def letterCombinations(self, digits):4         if digits=='':5             return []6         dic={
   '2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno',7             '7':'pqrs','8':'tuv','9':'wxyz'}8         return reduce(lambda X,Y: [pre+sub for pre in X for sub in dic[Y]], digits,[''])

在line 8 reduce函数的形式是：reduce(func, iterable, init) .

init是最开始给X的赋值，如果不指定init， 则X初始值默认是iterable的第一个元素。这里指定了，因此最开始X==[ '' ].

iterable是digits，也就是包含数字符号的字符串。因为指定了初始的X，所以Y的初始值为digits[0]...迭代过程中Y会变成digits[1], digits[2]...

func是一个lambda表达式：lambda X,Y: [pre+sub for pre in X for sub in dic[Y]]。其中包含一个列表推导式。相当于一个函数：

 

1 def func(X, Y):2     res=[ ]    3     for pre in X:4         for sub in dic[Y]:5             res.append(pre+sub)6     return res

 

在reduce函数中，上一次计算的结果会作为新的X。直到iterable（这里是digits）迭代结束。

 

3）回溯法。把问题的解空间用树的形式组织起来，在这棵虚拟的树上做深度优先遍历（DFS）。

 

1     def letterCombinations(digits): 2         if digits=='': 3             return [] 4         dic={
   '2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno', 5             '7':'pqrs','8':'tuv','9':'wxyz'} 6         res=[] 7         backTrack(dic, '', 0, digits, res) 8         return res 9         10     def backTrack(kvmap, localStr, index, digits, res):11         if index==len(digits):12             res.append(localStr)13         else:14             for c in kvmap[digits[index]]:15                 tmpStr=localStr+c16                 backTrack(kvmap, tmpStr, index+1, digits, res)

 

 

以上是基于递归的深度优先遍历。backTracking的退出条件是字符串的长度等于数字串的长度。