首页 > 代码库 > LeetCode - Restore IP Addresses

LeetCode - Restore IP Addresses

2024-07-08 08:48:21   215人阅读

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

搜索，递归，剪枝。
注意剪枝条件：1.每个域的数值不能大于255；2.有且刚好4个域；3.一个域的长度>=2时，不能以0开头。
不知道在这种找全部解，而不仅仅是证明是否有解的题目中，能否用动态规划类解？（二维矩阵的x轴是字符串，y轴是三个点）

class Solution:

    def doRestoreIpAddresses(self, prefix, num, s, start, fields):
        if start == len(s) - 1:
            results1 = [ ]
            results2 = [ ]
            if int(num + s[start]) <= 255 and 3 == fields and '0' != num:
                results1 = [prefix + s[start]]
            elif 2 == fields:
                results2 = [prefix + '.' + s[start]]
            return results1 + results2
        if int(num + s[start]) <= 255:
            results0 = [ ]
            results1 = [ ]
            if fields < 3:
                results0 = self.doRestoreIpAddresses(prefix + '.' + s[start], s[start], s, start + 1, fields + 1)
            if '0' != num:
                results1 = self.doRestoreIpAddresses(prefix + s[start], num + s[start], s, start + 1, fields)
            return results0 + results1
        elif fields < 3:
            results0 = self.doRestoreIpAddresses(prefix + '.' + s[start], s[start], s, start + 1, fields + 1)
            return results0
        else:
            return [ ]

    # @param s, a string
    # @return a list of strings
    def restoreIpAddresses(self, s):
        if len(s) < 4:
            return [ ]
        return self.doRestoreIpAddresses(s[0], s[0], s, 1, 0)


联系
我们