题目描述
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
1
2
| 输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
|
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
想法&尝试
这题我感觉也没什么很巧妙的办法吧，无非就是对求解的字符串集合不断的作笛卡尔积，什么意思呢？大概解释一下：
就拿题目示例为栗子，我求“23”的结果，那么我先求“2”，那么当前结果就是["a","b","c"]了，然后将digits中的第一位2删掉，再将["a","b","c"]与剩余数字串“3”对应的字符列表[“d”,”e”,”f”]做笛卡尔积，于是就得到了["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]。
就是这样，无非递归一下，注意递归的出口和入口（也就是边界条件啦）
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
26
| class Solution:
def __init__(self):
self.map = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
"6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
return self.product(digits, [])
def product(self, digits, result):
if digits == "":
return result
if not result:
result = [ch for ch in self.map[digits[0]]]
digits = digits[1:]
return self.product(digits, result)
newResult = []
for item in result:
for ch in self.map[digits[0]]:
newResult.append(item + ch)
digits = digits[1:]
return self.product(digits, newResult)
|
然后我运行，AC了，可是有点慢，52ms，超过了45%的人，于是我优化了一下，把字典直接变成列表，直接利用数字索引。
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
26
27
28
29
30
31
32
33
34
35
36
37
| class Solution:
def __init__(self):
self.map = ["abc", "def", "ghi", "jkl",
"mno", "pqrs", "tuv", "wxyz"]
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
return self.product(digits, [])
def product(self, digits, result):
"""
:param digits: 剩余未处理的数字串
:param result: 当前处理结果
:return:
"""
if digits == "":
return result
if not result:
result = [ch for ch in self.map[int(digits[0])-2]]
digits = digits[1:]
return self.product(digits, result)
newResult = []
for item in result:
for ch in self.map[int(digits[0])-2]:
newResult.append(item + ch)
digits = digits[1:]
return self.product(digits, newResult)
|
再提交，44ms，超过90%的人。~~
