复原IP地址

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是 有效的 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效的 IP 地址。

示例 1：

• 输入：s = "25525511135"
• 输出：["255.255.11.135","255.255.111.35"]

和切割回文字符串相似。切割问题可以抽象为树型结构，如图：

# 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
# 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，
# 但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
# 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，
# 这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。
from typing import List


class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        res = []
        # path = ''
        path = []
        self.backtracking2(s, 0, 0, path, res)
        return res
    #用来判断字符串中的IP是否合理，每个数0-255，不能0开头，用.分割
    def is_vaild(self, s, start, end):
        if start > end:
            return False
        #不能0开头
        if s[start] == '0' and start != end:
            return False
        #判断是否在0-255之间
        num = 0
        for i in range(start, end+1):
            #判断是否为数字
            if not s[i].isdigit():
                return False
            #判断是否在0-255之间
            num = num * 10 + int(s[i])
            if num > 255:
                return False
        return True
    #回溯函数，start_index表示当前遍历到字符串的哪个位置，path表示当前已经遍历的IP地址，还要有个pointNum的参数
    # 注意：由于Python字符串是不可变的，这里path + s[start_index:i + 1] + "."实际上是创建了一个新的字符串，
    # 所以在递归调用后不需要手动删除'.'
    # 如果path是可变类型，如列表，则需要在递归调用后进行回溯，即path.pop()
    # def backtracking(self, s, start_index, pointNum, path, res):
    #     #终止条件
    #     if pointNum == 3:
    #         #判断最后一段是否合理
    #         if self.is_vaild(s, start_index, len(s)-1):
    #             #最后一段合理则加入到path里
    #             path += s[start_index:]
    #             res.append(path)
    #         return
    #     #单层逻辑
    #     for i in range(start_index, len(s)):
    #         #判断当前字符串是否合理，切割的是start_index到i的字符串,左闭右闭
    #         if self.is_vaild(s, start_index, i):
    #             #回溯
    #             self.backtracking(s, i+1, pointNum+1, path + s[start_index:i+1] + '.', res)
    # 下述是用数组的方式
    def backtracking2(self, s, start_index, pointNum, path, res):
        if pointNum == 4:
            if start_index == len(s):
                res.append('.'.join(path))
            return
        for i in range(start_index, len(s)):
            if self.is_vaild(s, start_index, i):
                path.append(s[start_index:i+1])
                self.backtracking2(s, i+1, pointNum+1, path, res)
                path.pop()

#测试
if __name__ == '__main__':
    s = Solution()
    print(s.restoreIpAddresses('25525511135'))
#输出['255.255.11.135', '255.255.111.35']

 

原文地址：https://blog.csdn.net/weixin_52454379/article/details/142742441

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！