题目描述
样例
算法1
(回溯 Backtrace) $O(3^M ×4^N)$
· 定义函数 backtrack(combination, nextdigit)
,
1. 当 nextdigit
非空时,对于 nextdigit[0]
中的每一个字母 letter,执行回溯 backtrack(combination + letter,nextdigit[1:])
,
2. 直至 nextdigit
为空。
3. 最后将 combination
加入到结果中。
Python 代码
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits: return []
#学自题解区
phone = {'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 backtrack(conbination,nextdigit):
if len(nextdigit) == 0:
res.append(conbination)
else:
for letter in phone[nextdigit[0]]:
backtrack(conbination + letter,nextdigit[1:])
res = []
backtrack('',digits)
return res
算法2
(递归) $O(4^l)$
wzc题解
时间复杂度
参考文献
正在加紧修改中、c++转python3对于新手的我来说有点晕
C++ 代码
def
def solve(digits: str, d: int, cur: str):
if d == len(digits):
res.append(cur);
return
curnum = []
curnum.append(digits[d] - '0')
for i in range(0, i < len(digits[curnum])):
solve(digits, d + 1, cur + digit[curnum][i])
res = ''
if digits == "":
return res
cur = 'a'
digit = {'....//待修改}
solve(digits, 0, "")
return res
【队列】queue!
使用队列,
1. 先将输入的 digits 中第一个数字对应的每一个字母入队,
2. 然后将出队的元素与第二个数字对应的每一个字母组合后入队…直到遍历到 digits 的结尾。
3. 最后队列中的元素就是所求结果。
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits: return []
phone = ['abc','def','ghi','jkl','mno','pqrs','tuv','wxyz']
queue = [''] # 初始化队列
for digit in digits:
for _ in range(len(queue)):
tmp = queue.pop(0)
for letter in phone[ord(digit)-50]:# 这里我们不使用 int() 转换字符串,使用ASCII码
queue.append(tmp + letter)
return queue