本文共 2096 字,大约阅读时间需要 6 分钟。
作为一道经典的Medium难度的问题,本题的考点在于回溯法(Backtracking
),递归(Recursion
),深度搜索(DFS
)。但是可能你没有想到,这道题还可以用普通迭代(Iteration
,更直接地说for/while
循环)的方法来解。下面让我们一起来看看这两种解法是如何实现的吧。
注意:文章中一切注解皆为Python代码
题目非常简单。在传统电话按键上,数字键下面都对应着一些字母,数字按键2到9涵盖了所有26个英文字母。题目的输入参数是一个仅包含数字2到9的字符串,需要我们输出这些数字各自对应的字母能构成的所有组合。
最简单直观的解法就是把这题看作可包含重复字符,可变长度的字符串排列(permutation
),可以想象成是的一种变体。
要我说解法并不复杂,每一次递归中,逐个加入相对应的字母到cur
中;将字符串长度+1
,直到长度等于字符串长度时,添加入结果(ans
)中。最终最差时间复杂度为O(4^N)
,因为最终长度为N
,每个位置都有4个字母可以选(7和9对应四个字母,其他对应三个字母)。
class Solution: def letterCombinations(self, digits): table = { '2':"abc", '3':"def", '4':"ghi", '5':"jkl", '6':"mno", '7':"pqrs", '8':"tuv", '9':"wxyz" } def dfs(ans, cur, idx): nonlocal digits if idx == len(digits): ans.append(cur) else: for letter in table[digits[idx]]: dfs(ans, cur+letter, idx+1) return ans return dfs([], "", 0) if digits else []
迭代解法看似很复杂,但其实真的不难理解。
时间复杂度为O(N* 4^N)
,其中N
是为了遍历每一个数字,ans
最终会有4^N
个,因此时间复杂度稍微高一些。不过考虑到这题的输入尺寸是
0 <= digits.length <= 4
因此Python程序运行一遍其实也只需要几十毫秒。
迭代解法过程如下:
ans
;digit
,把ans
中的每个可能结果和这个数字对应的字母们table[digit]
做笛卡尔乘积(Cartesian product
),会得到一个新的ans
ans
class Solution: def letterCombinations(self, digits): if not digits: return [] table = { '2':"abc", '3':"def", '4':"ghi", '5':"jkl", '6':"mno", '7':"pqrs", '8':"tuv", '9':"wxyz" } ans = list(table[digits[0]]) for digit in digits[1:]: ans = [exist + c for exist in ans for c in table[digit]] # 这一句等同于下面五句 # tmp = [] # for exist in ans: # for c in table[digit]: # tmp.append(exist + c) # ans = tmp return ans
这题不管是用递归还是迭代,基本都属于一种暴力解决的状态。这和题目要求是有关系的,因为我们必须输出所有可能的组合。一提到【找出所有组合】,更多的想到的是【递归】。有趣的地方在于,一旦我们先入为主的用递归解决了问题,就很难想象到这题还可以用迭代的方式实现;毕竟【迭代】和【找出所有组合】这种需求经常不会直接联系起来。
我想值得学习的就是,尽管迭代这种方式更加符合直觉,更好理解,但用力去了解把递归化为迭代的方式,也是一份十足的收获。
转载地址:http://oqgoi.baihongyu.com/