day28 回溯算法part4 代码随想录算法训练营 93. 复原 IP 地址

题目：93. 复原 IP 地址

我的感悟：

• 加油！

理解难点：

• 开始没理解，start_index的含义
• start_index是切割后的位置信息。

代码难点：

代码示例：

from typing import List


class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        # 找3个分割点？
        # 最后一个分割点的时候，判断path，加入res
        # 不符合规则的就跳过
        res = []
        self.backtracking(s, 0, [], res)
        return res

    def backtracking(self, s, start_index, path, result):
        if len(path) > 4:  # 异常情况
            return
        if len(path) == 4 and start_index == len(s):  # start_index是切割后的结果
            result.append(".".join(path))
            return

        for i in range(start_index, len(s)):
            # 这一步是剪枝 if i - start_index > 2: continue
            if self.is_valid(s[start_index:i + 1]):
                path.append(s[start_index:i + 1])
                self.backtracking(s, i + 1, path, result)
                path.pop()

    def is_valid(self, s):
        if s[0] == '0' and len(s) > 1:
            return False
        if int(s) > 255:
            return False
        return True


if __name__ == '__main__':
    obj = Solution()
    s = "25525511135"
    res = obj.restoreIpAddresses(s)
    print(res)

通过截图：

扩展写法：

资料：

网友的答案（更好理解）：https://blog.csdn.net/i_do_i/article/details/135997951

题目链接/文章讲解：https://programmercarl.com/0093.%E5%A4%8D%E5%8E%9FIP%E5%9C%B0%E5%9D%80.html

视频讲解：https://www.bilibili.com/video/BV1XP4y1U73i/