题解 | 数字字符串转化成IP地址

方法一：递归+回溯（扩展思路）

将一个只包含数字的字符串转化成IP地址的形式，可以使用**深度优先搜索（DFS）**的方法。IP地址由四段数字组成，每段数字的范围是0到255，并且不能含有前导0。我们需要在字符串中插入三个点，使得每段数字都符合IP地址的要求。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @return string字符串一维数组
#
class Solution:
    def restoreIpAddresses(self , s: str) -> List[str]:
        # write code here
        n, ans = len(s), []
        def backtrack(start,path):
            if len(path)==4:#当被分为了四段时
                if start==n:#如果分段符号已经到了长度n
                    ans.append('.'.join(path))
                return
            for i in range(1,4):#每段的长度，1-3
                if start+i<=n:#控制每段长度
                    segment = s[start:start+i]
                    if segment[0]=='0' and len(segment)>1 or int(segment)>255:#查看当前段是否满足要求
                        continue
                    backtrack(start+i,path+[segment])#寻找下一段
        backtrack(0,[])
        return ans

在这个代码中，我们定义了一个递归函数backtrack，它接受当前的起始位置和已经形成的路径作为参数。我们在每个位置尝试插入一个点，并检查形成的段是否有效。如果有效，则继续递归，直到形成四段有效的IP地址。

重要考虑事项

前导零：如果一个段的长度大于1且以'0'开头，则该段无效。范围检查：每个段的值必须在0到255之间。递归终止条件：当路径长度为4且已经遍历完字符串时，形成一个有效的IP地址。

通过这种方法，我们可以生成所有可能的有效IP地址，并返回结果列表。

牛客针对本题目也有专门的讲解：题解 | #数字字符串转化成IP地址#