吴良超的学习笔记

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

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