首页 > 其他 > 详细

LeetCode - Restore IP Addresses

时间:2014-06-16 19:24:11      阅读:391      评论:0      收藏:0      [点我收藏+]

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)

LeetCode - Restore IP Addresses,布布扣,bubuko.com

LeetCode - Restore IP Addresses

原文:http://blog.csdn.net/nerv3x3/article/details/31068775

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!