LeetCode 解题报告 (17)-- 电话数字组合成的不同字符串

发表于 标签 ，

原题如下:
>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"].

题目很好理解，就是组合出所有可能结果即可。每个数字写一个 for 循环即可，但是在程序运行前我们无法知道到底输入有几个数字，下面给出两个方法解决这个问题。

方法一是回溯法，每次选择当前数字的一个字符，然后将下一个数字作为当前数字，直到所有的数字都遍历完即可。实现的代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):  
    numDict ={'2':['a','b','c'],'3':['d','e','f'],'4':['g','h','i'],'5':['j','k','l'],'6':['m','n','o'],'7':['p','q','r','s'],'8':['t','u','v'],'9':['w','x','y','z']}  
    def letterCombinations(self, digits):  
        """  
        :type digits: str  
        :rtype: List[str]  
        """  
        result = []  
        self.helper(0, digits, '', result)  
        return result

    def helper(self, index, digits, tmp, result):  
        if index == len(digits):  
            if tmp: # empty string  
                result.append(tmp)  
            return  
        for char in Solution.numDict[digits[index]]:  
            self.helper(index+1, digits, tmp+char, result)

除了回溯法，还可以通过顺序的合并，考虑每次对两个 string list 进行合并，合并后作为一个 string list，再和后面的一个数字表示的 string list 合并，就这样一直循环下去直到最后一个数字

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#encoding:utf-8  
class Solution(object):  
    def letterCombinations(self, digits):  
        """  
        :type digits: str  
        :rtype: List[str]  
        """  
        numDict ={'2':['a','b','c'],'3':['d','e','f'],'4':['g','h','i'],'5':['j','k','l'],'6':['m','n','o'],'7':['p','q','r','s'],'8':['t','u','v'],'9':['w','x','y','z']}

        result = []  
        if len(digits)==0:  
            return result  
        # 先将第一位对应的字符复制给result，防止调用函数combine2StrList时一开始result为空  
        result = numDict[digits[0]]  
        for i in range(1,len(digits)):  
            result = self.combine2StrList(result,numDict[digits[i]])  
        return result


    def combine2StrList(self,s1,s2):  
        mix =[]  
        for i in range(len(s1)):  
            for j in range(len(s2)):  
               mix.append(s1[i]+s2[j])  
        return mix

如有更好的解法，欢迎交流