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],

]

相关单词