回溯算法-复原IP地址

忘是亡心i 2023-02-15 01:26 44阅读 0赞

leetcode 93 [复原IP地址][IP]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pheV93b25kZXI_size_16_color_FFFFFF_t_70]  
首先一个正确有效的IP地址，由4个整数构成，介于0-255，也就是说每个整数长度介于1-3，那么整个IP的有效长度(不包含’.’）就介于4-12，这就是对于给出的字符串长度不再这个范围之内，就不用回溯了。  
第二点，字符串中有0的情况，比如’010010’，在回溯的时候，就可能出现’001’这样的选择，显然这种情况是不正确的，不能以0开头，除非就只有一个0，这里就是剪枝操作了，也就是一旦出现这样的选择，后面就不用再进行回溯。  
第三，递归终止条件：形成4个整数，并且这4个整数长度加起来为原数字字符串的长度。

def restoreIpAddresses(self, s: str) -> List[str]:
            n = len(s)
            if n < 4 or n > 12:
                return []
            res = []
            def backtrace(start, tmp, S):
                #递归终止条件
                if len(tmp) == 4 and len(''.join(tmp)) == n:
                    res.append('.'.join(tmp))
                    return
                for i in range(start, n):
                	#如果加上当前选择大于255，那么直接从当前选择重新开始，构造下一个整数
                    if int(S + s[i]) > 255:
                        S = s[i]
                    else:
                        S += s[i]
                    #处理以0开头的情况，比较整型化前后是否相同，
                    #比如'001'，int('001')就是1，如果不一样
                    #那就是无效的了，无需进行后面的回溯过程
                    if S[0] == '0':
                        if S != str(int(S)):
                            continue
                    #标准回溯过程
                    tmp.append(S)
                    _S, S = S, ''
                    backtrace(i+1, tmp, S)
                    tmp.pop()
                    S = _S
            backtrace(0, [], '')
            return res

整个过程除了剪枝的操作，其他的就是模板的东西，没啥特别的，很有套路是不是。。。做选择的过程有点像求子集，每次回溯起点从i+1开始  
再来看一道题，代码真的是基本一样。。  
leetcode 309 [累加数][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pheV93b25kZXI_size_16_color_FFFFFF_t_70 1]  
同样要对以0开头的情况进行剪枝，操作和上一道题完全一样。  
这道题另外需要注意的是，由前两个数可以确定第三个数，如果当前的整个数，并不等于其前两个数之后，那么说明，这种组合是错误的，那么后面的就没有必要再进行回溯了，这是第二个需要剪枝的。

class Solution:
        def isAdditiveNumber(self, num: str) -> bool:
            n = len(num)
            if n < 3:
                return False
            res = []
            def backtrace(start, tmp, s):
            	#终止条件
                if len(tmp) >= 3 and len(''.join(tmp)) == n:
                    tmp = [int(each) for each in tmp]
                    for i in range(2, len(tmp)):
                        if tmp[i-1] + tmp[i-2] != tmp[i]:
                            return False
                    return True
                for i in range(start, n):
                    s += num[i]
                    #以0开头的情况，一样的
                    if s[0] == '0':
                        if s != str(int(s)):
                            continue
                    #如果当前的数不等于前两个数之和，后面就不用再回溯，直接往后移位
                    if len(tmp) > 2 and int(tmp[-1]) != int(tmp[-3]) + int(tmp[-2]):
                        continue
                    #回溯
                    tmp.append(s)
                    _s, s = s, ''
                    if backtrace(i+1, tmp, s):
                        return True
                    s = _s
                    tmp.pop()
                return False
            if backtrace(0, [], ''):
                return True
            return False

代码是不是基本一样，如出一辙。以不变应万变(狗头)

[IP]: https://leetcode-cn.com/problems/restore-ip-addresses/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pheV93b25kZXI_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200604103928139.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pheV93b25kZXI=,size_16,color_FFFFFF,t_70
[Link 1]: https://leetcode-cn.com/problems/additive-number/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pheV93b25kZXI_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200604110058626.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pheV93b25kZXI=,size_16,color_FFFFFF,t_70