17.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. Return the answer in any order.
给定一组2-9组成的字符串，返回所有可能的字符组合。
Constraints:
0 <= digits.length <= 4
digits[i] is a digit in the range ['2', '9'].
Example 1:
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:
Input: digits = ""
Output: []
Example 3:
Input: digits = "2"
Output: ["a","b","c"]
思考
思考之前先创建一个数组：可以通过 ‘数字-2’ 对应下标
_char = [['a','b','c'], ['d','3','f'], ['g','h','i'], ['j','k','i'], ['m','n','o'], ['p','q','r','s'], ['t','u','v'],['w','x','y','z']]
1.暴力递归
遍历几个数字，对数字包含的内容再次遍历。
class Solution:
_char = [['a','b','c'], ['d','e','f'], ['g','h','i'], ['j','k','l'], ['m','n','o'], ['p','q','r','s'], ['t','u','v'],['w','x','y','z']]
def _join(self,c,s):
return [c+i for i in s]
def letterCombinations(self, digits: str) -> List[str]:
ret = []
if len(digits)>1:
tmp = self._char[int(digits[0])-2]
for i in range(len(tmp)):
ret.extend(self._join(tmp[i], self.letterCombinations(digits[1:])))
elif len(digits) == 1:
ret = self._char[int(digits[0]) - 2]
return ret
怎么说呢，终于有一个可以跑完的暴力法了。
答案解析
回溯法
所有解，肯定的需要用到搜索算法：深度优先，广度优先。
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return list()
phoneMap = {
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz",
}
groups = (phoneMap[digit] for digit in digits)
return ["".join(combination) for combination in itertools.product(*groups)]
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return list()
phoneMap = {
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz",
}
def backtrack(index: int):
if index == len(digits):
combinations.append("".join(combination))
else:
digit = digits[index]
for letter in phoneMap[digit]:
combination.append(letter)
backtrack(index + 1)
combination.pop()
combination = list()
combinations = list()
backtrack(0)
return combinations
第一个给的是一行代码行数比较少的解决方案，第二个是代码比较清晰的版本。
从第二个版本来看，用字典来存储键值对，且设置了一个回溯函数。
函数在内部使用了递归方法。使用的是深度优先算法，将一条匹配路径下的每一种可能性走一次，然后合并成字符串并append到返回值里面。
总结
感觉官方给出的解答没有我的递归简单，但是用到了深度优先。相当于是带我回顾了一遍深度优先算法。
问题来了。。。我的递归算是什么优先？？
今天才发现还有一个测试代码的地方，这样的话就会很大的减少自己提交出错率。。
