Python 刷Leetcode题库，顺带学英语单词（4）

Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.  [#17]

Example:
Input: "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.

题意：只包含2~9数字的字符串，根据电话机按键的对应关系，给出所有可能的字母组合。

先建一个电话机的键值映射，只有2~9对应a~z，1无任何对应，0一般表示空格：

>>> keyMap = ''.join([chr(i) for i in range(97,122) if i!=115])
>>> keyMap = [keyMap[i:i+3] for i in range(0,len(keyMap),3)]
>>> keyMap[-1]+='z'
>>> keyMap[-3]+='s'
>>> keyMap = [' ',''] + keyMap
>>> keyMap[2]
'abc'
>>> [keyMap[int(i)] for i in '323679']
['def', 'abc', 'def', 'mno', 'pqrs', 'wxyz']
>>> 

再引入一个第三方库 allpairpy 方便解题，其中的AllPairs()函数可以轻松列出所有字母组合(letter-pairs)。没有安装的在dos窗口中，运行 pip install allpairpy 。

D:\>pip install allpairspy
Collecting allpairspy
  Downloading allpairspy-2.5.0-py2.py3-none-any.whl (8.7 kB)
Requirement already satisfied: six<2.0.0,>=1.10.0 in d:\python\lib\site-packages (from allpairspy) (1.15.0)
Installing collected packages: allpairspy
Successfully installed allpairspy-2.5.0

最后，代码如下：

>>> from allpairspy import AllPairs
>>> def LetterCombinate(numString):
	keyMap = ''.join([chr(i) for i in range(97,122) if i!=115])
	keyMap = [keyMap[i:i+3] for i in range(0,len(keyMap),3)]
	keyMap[-1]+='z'
	keyMap[-3]+='s'
	keyMap = [' ',''] + keyMap
	num = numString.replace('1','')
	lst = [keyMap[int(i)] for i in num]
	tmp = ['']
	for i in range(len(lst)):
		res = []
		for pair in AllPairs([tmp,lst[i]]):
			res.append(''.join(pair))
			tmp = res
	return sorted(res)

>>> LetterCombinate('23')
['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
>>> LetterCombinate('52013')
['ja d', 'ja e', 'ja f', 'jb d', 'jb e', 'jb f', 'jc d', 'jc e', 'jc f',
 'ka d', 'ka e', 'ka f', 'kb d', 'kb e', 'kb f', 'kc d', 'kc e', 'kc f',
 'la d', 'la e', 'la f', 'lb d', 'lb e', 'lb f', 'lc d', 'lc e', 'lc f']
>>> 

Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.   [#77]

Example:
Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

相关单词