例如,让我们考虑一个任务,我们需要找到给定字符串的所有排列,保留字符序列但改变大小写。
这是没有回溯的解决方案.pop()
:
def letterCasePermutation(S):
"""
:type S: str
:rtype: List[str]
"""
def backtrack(sub="", i=0):
if len(sub) == len(S):
res.append(sub)
else:
if S[i].isalpha():
backtrack(sub + S[i].swapcase(), i + 1)
backtrack(sub + S[i], i + 1)
res = []
backtrack()
return res
这是一个解决方案.pop()
:
def letterCasePermutation(s):
def backtrack(idx, path):
if idx == n:
res.append("".join(path))
return
ele = s[idx]
if ele.isnumeric():
path.append(ele)
backtrack(idx + 1, path)
path.pop()
else:
path.append(ele.lower())
backtrack(idx + 1, path)
path.pop()
path.append(ele.upper())
backtrack(idx + 1, path)
path.pop()
n = len(s)
res = []
backtrack(0, [])
return res
两个代码示例都是回溯,还是应该将第一个代码示例称为 DFS,将第二个代码示例称为回溯?
对于回溯(以及大多数递归函数),每个函数调用的关键不变量是它不会破坏父调用中的状态。
这应该具有直观意义,因为递归依赖于自相似性。如果调用堆栈中其他地方发生不可预测的状态更改,从而影响与祖先调用共享的数据结构,则很容易看出自相似性的属性是如何丢失的。
递归函数调用通过将框架推到调用栈,根据需要在本地操作状态,然后弹出调用堆栈。在返回父框架之前,子调用负责恢复状态,以便从父调用框架的角度来看,执行可以继续进行,而不会被链上的某个随机祖先调用造成任何令人惊讶的状态修改。
打个比喻,您可以将每个调用帧视为遍历以下情节帽子里的猫 or 冒险生意如果主角弄乱了(在他们的调用框架中),那么必须在故事结束(函数返回)之前恢复秩序。
现在,鉴于这个高级目标,如您的代码片段所示,有多种方法可以实现它。一种方法是分配某种数据结构,例如列表对象一次,然后push
(append
) and pop
在每个调用帧上,镜像调用堆栈。
另一种方法是在生成子调用时复制状态,以便每个帧接收相关数据的最新版本,并且它们所做的任何修改都不会扰乱其父状态。与改变单个数据结构相比,这通常需要更少的簿记,并且不太容易受到细微错误的影响,但由于内存分配器和垃圾收集器操作以及为每个帧复制数据结构,往往会产生更高的开销。
简而言之,不要混淆保持每个调用帧状态完整的高级目标和代码如何实现它。
据,直到...为止回溯 versus DFS,我认为回溯是一种专门的 DFS,它会修剪掉启发式确定不值得进一步探索的搜索树分支,因为它们无法得出解决方案。和以前一样,代码如何实际实现状态恢复以实现回溯(复制数据结构或推送/弹出显式堆栈)不应改变它是相同基本算法技术的事实。
我见过术语“回溯”应用于这样的排列算法。尽管该术语可能相当常见,但它似乎是一种误用,因为排列算法是一种全状态递归遍历,它将始终访问树中的所有节点,并且不会像回溯那样进行任何智能启发式修剪。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)