LeetCode 93.复原IP地址 Python题解

复原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地址。
给定一个只包含数字的字符串s，用以表示一个IP地址，返回所有可能的有效IP地址，
这些地址可以通过在s中插入'.'来形成。你不能重新排序或删除s中的任何数字。你可以按任何顺序返回答案。
"""


class Solution:
    def restoreIpAddresses(self, s):
        du = 4
        ans = list()
        segments = [0] * du

        def dfs(pointer, step):
            # 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案
            if pointer == du:
                if step == len(s):
                    ipAddr = ".".join(str(seg) for seg in segments)
                    ans.append(ipAddr)
                return

            # 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提退出
            if step == len(s):
                return

            # 0记录跳过
            if s[step] == "0":
                segments[pointer] = 0
                dfs(pointer + 1, step + 1)
                return

            # 一般情况，枚举每一种可能性并递归
            addr = 0
            for segEnd in range(step, len(s)):
                addr = addr * 10 + (ord(s[segEnd]) - ord("0"))
                if 0 < addr <= 0xFF:
                    segments[pointer] = addr
                    dfs(pointer + 1, segEnd + 1)
                else:
                    break

        dfs(0, 0)
        return ans


s = "25525511135"
a = Solution()
print(a.restoreIpAddresses(s))

# 其实这道题还是很简单的，但是有一个思考空间就是说字符串S怎么循环查找
# 这个是需要思考的，其实也还好，因为其实是循环问题思考一下就可以
# 就是普通的递归与回溯了