复原IP地址

Leetcode Link: 93. 复原 IP 地址 - 力扣（LeetCode）

题目

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址 这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

解法一

思路：回溯，属于切割问题，下面是我自己的思路

本题主要是细节比较多，需要思考很多的问题

本题满足题目要求的条件：

1. path 中恰好有 4 个整数 and 输入的 s 中的东西全部用完 and 所有的整数都满足题目要求（没有 0 开头的，没有>255 的）

本题回溯需要终止的情况

1. path 中整数即将超过 4 个
2. 当前的 IP 整数不是单独的 0 但是却以 0 开头
3. 当前IP的位数 >3
4. 当前 IP 整数数字 > 255
5. 切割线越界

由于在判定回溯终止的时候，已经考虑部分条件，因此实际上满足本题题目要求的条件可以简化为：path 中恰好有 4 个整数 and 输入的 s 中的东西全部用完

本题的细节较多，难点是如何在合适的位置插入对应的判断语句来控制回溯的停止和结果的添加。

题解：

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        def backtracking(start_index):
            nonlocal s, res, path
            # 满足题目要求
            if start_index == len(s) and len(path)==4:
                tmp = ".".join(path)
                res.append(tmp)
                return
            # 4. 切割线越界 - 情况 1
            elif start_index >=len(s):
                return
            # 1. 超过4个整数
            elif len(path) == 4:
                return
			# 这里直接控制位数，可以少判断一个回溯停止情况 (3
            for i in range(3):
                # 分割线位置
                parti_line = start_index+i
 
                # 5. 分割线越界 - 情况2
                if parti_line > len(s):
                    return
                
                cur = s[start_index:parti_line+1]
 
                # 2. 0 开头的非一位数字非法，停止回溯
                if i>0 and cur[0] == '0':
                    return
                # 4. 当前IP值>255，停止回溯
                elif int(cur) > 255:
                    return
 
                path.append(cur)
                backtracking(parti_line+1)
                path.pop()
        
        res = []
        path = []
        backtracking(0)
        return res   

上面的思考中，回溯停止条件 3) 和 4）是可以合并的，只要判断 >255 就行，这样的话也不用 i 来控制位数了

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        def backtracking(start_index):
            nonlocal s, res, path
            # 满足题目要求
            if start_index == len(s) and len(path)==4:
                tmp = ".".join(path)
                res.append(tmp)
                return
            # 4. 切割线越界, 停止回溯
            elif start_index >=len(s):
                return
            # 1. 超过4个整数
            elif len(path) == 4:
                return
 
            for i in range(start_index, len(s)):
                cur = s[start_index:i+1]
                
                if len(cur)>1 and cur[0] == '0': # 2. 0 开头的非一位数字非法，停止回溯
                    return
                elif int(cur) > 255: # 4. 当前IP值>255，停止回溯
                    return 
 
                path.append(cur)
                backtracking(i+1)
                path.pop()
        
        res = []
        path = []
        backtracking(0)
        return res   

---

复习时的新代码

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        path = []
        res = []
        def bkt(i):
            # 停止回溯：当前i超过s
            if i >= len(s):
                return
            # 停止回溯：如果当前path中已经含有3个了，只需要判定最后的部分是不是合规就行
            if len(path) == 3:
                if i == len(s) -1:  # 只剩一个的时候肯定可以
                    path.append(s[i:])
                    res.append(path.copy())
                    path.pop()
                elif i < len(s)-1 and s[i] != '0' and 0<int(s[i:])<=255: # 剩>1个时需要避免先导0和控制大小
                    path.append(s[i:])
                    res.append(path.copy())
                    path.pop()
                else: # 其他都违规，
                    return
 
            if s[i] == '0':  # 如果是0则只能自己一位，不能有先导0
                path.append(s[i])
                bkt(i+1)
                path.pop()
            else:  # 没有先导0就可以确定下次的分割点。
                for next_i in range(i+1, len(s)):
                    if 0 < int(s[i:next_i])<=255:
                        path.append(s[i:next_i])
                        bkt(next_i)
                        path.pop()
                    else:
                        break
    
        bkt(0)
        return ['.'.join(tmp) for tmp in res]

启发和联系

面对一个回溯的问题，可以画出树型结构来分析问题，并仔细列出下面两个问题的情况

1. 问题答案的条件是什么，添加到结果之后是停止回溯还是继续往下走？
2. 停止回溯的条件是什么？可能有很多，一一列出来

思考完后上面的问题之后，开始思考所有条件能不能合并？在哪里进行上面一些问题的判断？