[LeetCode]93. 复原IP地址（Restore IP Addresses）

题目描述

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

示例:

输入: “25525511135”
输出: [“255.255.11.135”, “255.255.111.35”]

解题思路

DFS。搭配较多的剪枝可加快速度。

代码

Python 3.6

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        length = len(s)
        if length < 4 or length > 12:
            return []
        res = []
        self.__dfs(s, 0, length, [], res)
        return res
    
    def __dfs(self, s, start, length, path, res):
        blank = 4 - len(path)
        if blank == 0:
            if start >= length:
                res.append(".".join(path.copy()))
            return
        if (length - start < blank) or (length - start > 3 * blank):
            # 剩下的数字比空还少 或 比3*空还多
            return
        for i in range(1, 4):
            end = start + i
            if end > length or int(s[start:end]) > 255 or (i > 1 and s[start:end][0] == "0"):
                # 不合法：超过255、非单个数字且首位为0
                break
            path.append(s[start:end])
            self.__dfs(s, end, length, path, res)
            path.pop()

执行用时 : 52 ms
内存消耗 : 13.8 MB