今天练习-回溯算法-93. 复原 IP 地址

注意点&感悟：

• 难吗？不难。难的是克服畏难的心里。

题目链接：93. 复原 IP 地址

自己独立写的代码：

from typing import List


class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        res = []
        self.backtracking(s, 0, [], res)
        return res

    def backtracking(self, s, start_index, path, result):
        # 退出条件1: 不符合要求的
        if len(path) > 4:
            return
        # 退出条件2: 找到满足要求的了
        if start_index == len(s) and len(path) == 4:  # 如果切到末尾了,并且path里面存的值长度等于4了
            result.append(".".join(path))  # 添加进去
            return
        # 核心代码
        for i in range(start_index, len(s)):
            # 多了一层判断合法性 s[start_index:i+1]  # 注意是start_index为开始条件,要判断[2551]是合法的不
            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:  # 01是不合法的,0是合法的
            return False
        if int(s) > 255:
            return False
        return True


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