leetcode 93. 复原IP地址 python 我最不会的回溯来了!

回溯题目我一直不太会。个人理解回溯是一种解题思路,可以通过递归来实现。但有的字符串的题目,比如131. 分割回文串,可以主观通过理解成新加入一个字符或者新加入一段字符来解释,我就可以通过递归写出来,但像leetcode 93. 复原IP地址我就有些摸不着思路。
最后参考网络上的一篇博客,一边看一边写的结果是这样:
leetcode 93. 复原IP地址 python 我最不会的回溯来了!
这个回溯其实就是探索可能满足的条件,如果一定不满足就返回上一级,还是很好理解的。但过一天我复现的时候,主体部分是这么写的:
leetcode 93. 复原IP地址 python 我最不会的回溯来了!leetcode 93. 复原IP地址 python 我最不会的回溯来了!
主观看起来并没有任何不对,但执行结果是这样:
leetcode 93. 复原IP地址 python 我最不会的回溯来了!
看起来并没有回溯!
我一直以为是判断条件出了问题,就一直更改判断条件。改完发现还是不对,后来又怀疑是不应该return re.顺路说一下,之前的结果不用return 应该是在同一类里面变量是可以用的,但删掉return re结果还是没有改善。到底哪里出了问题呢?
只能一步步更改,我发现改到这一步结果对了!
leetcode 93. 复原IP地址 python 我最不会的回溯来了!
刚开始并不能理解,只能debug一步步看。发现唯一的区别就是,不满足条件时就会回到上一级,每次回溯都会先执行这两句赋值,然后把当前的这两个值改了再返回上一级调用。比如,把finished和left根据当前的值改了,就回不到上一级了!!!就是,**在返回上一级之前,这两个参数已经改变了,所以其实没有回溯的效果。**所以结果会出错!