python 输入字符串生成所有有效的IP地址(LeetCode 93号题)

这里我将给出详细的Python代码和解析来实现LeetCode 93号题，即输入一个字符串生成所有有效的IP地址。

问题描述

给定一个只包含数字的字符串"25525511135",将它转换成所有可能的IP地址返回。有效的IP地址由四个0到255之间的整数表示，并且以“点”隔开。例如，字符串"25525511135"可以转换为如下所有有效的IP地址：

[
  "255.255.11.135",
  "255.255.111.35"
]

解题思路

这道题是一道比较典型的DFS深度优先搜索题，我们可以把给定的字符串划分成四个部分，分别表示ip地址中的四个整数。然后对于每一个整数，枚举它可能的取值，直到形成一个完整的ip地址。

具体来说，我们可以在dfs递归函数中维护一个变量k，它表示我们已经凑出了ip地址中的前k个整数。同时，为了避免出现像“012”这样的不合法ip地址，我们还需要一个变量last，它表示在向第k+1个整数尝试添加数字时，在原字符串中的起始位置。

代码如下：

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

    def dfs(self, s, k, path, res):
        if k == 4:  # 找到了四个整数，添加到结果中
            if not s:  # 如果原字符串也用完了，就添加
                res.append('.'.join(path))
            return

        for i in range(1, 4):
            # 尝试添加新的整数
            if i <= len(s):
                # 新的整数不能以0开头，除非它本身就是0
                if i == 1 or (i > 1 and s[0] != '0'):
                    # 新的整数必须在[0, 255]范围内
                    if int(s[:i]) <= 255:
                        # 将新整数添加到路径中，并递归查找下一个整数
                        self.dfs(s[i:], k + 1, path + [s[:i]], res)

这个代码中，我们定义了一个抽象数据结构path，它表示生成的ip地址，然后每个递归分支会尝试添加ip地址的下一个整数。

注意，由于每个整数只可能由1、2、或3个数字组成，所以我们在进行枚举时，只需枚举长度在[1,3]之间的所有子串即可。

示例说明

接下来我们对两个示例进行说明。

示例1

Input: s = "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

当s="25525511135"时，修正上述代码中的函数，进行DFS调用，生成合法的IP即可，代码如下:

s = Solution()
s.restoreIpAddresses("25525511135")
# Out: ["255.255.111.35", "255.255.11.135"]

示例2

Input: s = "0000"
Output: ["0.0.0.0"]

当s="0000"时，修正上述代码中的函数，进行DFS调用，生成合法的IP即可，代码如下:

s = Solution()
s.restoreIpAddresses("0000")
# Out: ["0.0.0.0"]

希望这些说明可以帮助您理解并解决这道难度为中等的LeetCode 93号题。