题解 |简洁实现 #数字字符串转化成IP地址#

可以将寻找合法 IP 地址的过程看做建立树的过程，该树一共有四层，分别对应IP地址的四个字段，每当找到一个符合要求的节点，则树加深一层（递归深入一层），并在遍历的过程中记录建立树的路径，当所有字符都走完且树的深度为4时（等价于一条路径长度为4），代表找到了一个合法的IP地址；

基于上述思路，得到的实现比现有题解简洁很多：

class Solution:
    def restoreIpAddresses(self , s: str) -> List[str]:
        # write code here
        def backtrack(start, path):
            # 如果已经遍历完了字符串，并且路径长度为4，那么就是一个解
            if start == len(s) and len(path) == 4:
                result.append('.'.join(path))
                return
            # 如果剩下的字符串长度超过了IP地址要求（每个字段长度不超过3位），直接返回
            if len(s) - start > 3 * (4 - len(path)):
                return
            # 尝试当前字段的每一种可能的长度（1到3）
            for i in range(1, 4):
                # 已经遍历完了当前字符串，直接返回
                if start + i > len(s):
                    return
                # 如果是0开头的数字，且长度大于1，那么跳过（比如'01'不合法）
                if i > 1 and s[start] == '0':
                    return
                # 截取当前部分
                part = s[start:start + i]
                # 如果当前部分合法，那么加入路径中，构建树的下一层
                if 0 <= int(part) <= 255:
                    backtrack(start + i, path + [part])
        result = []
        backtrack(0, [])
        return result