Leetcode 93. Restore IP Addresses

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

解析：Version 1，容易想到的方案，枚举.所有可能的位置，然后对四个数字进行检查，如果都合法，则为合法的IP地址，也可以枚举数字。

• Version 1

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        result = []
        chars = list(s)
        length = len(s)
        for i in range(1, length):
            for j in range(i+1, length):
                for k in range(j+1, length):
                    num1 = ''.join(chars[:i])
                    num2 = ''.join(chars[i:j])
                    num3 = ''.join(chars[j:k])
                    num4 = ''.join(chars[k:])
    
                    if self.validify(num1) and self.validify(num2) and self.validify(num3) and self.validify(num4):
                        ip_address = num1 + '.' + num2 + '.' + num3 + '.' + num4
                        result.append(ip_address)
        return result


    def validify(self, num):
        if len(num) == 0:
            return False
        elif len(num) > 1 and num[0] == '0':
            return False
        elif int(num) > 255:
            return False
        return True

解析：Version 2，在Version 1的基础上进行剪枝，每轮循环的遍历数量可以再减少一些，当出现数字不合理时，则进行下一次循环。

• Version 2

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        result = []
        chars = list(s)
        length = len(s)

        for i in range(1, 4):
            num1 = ''.join(chars[:i])
            if not self.validify(num1):
                continue
            for j in range(i+1, i+4):
                num2 = ''.join(chars[i:j])
                if not self.validify(num2):
                    continue
                for k in range(j+1, j+4):
                    num3 = ''.join(chars[j:k])
                    num4 = ''.join(chars[k:])
                    if self.validify(num3) and self.validify(num4):
                        ip_address = num1 + '.' + num2 + '.' + num3 + '.' + num4
                        result.append(ip_address)
        return result


    def validify(self, num):
        if len(num) == 0:
            return False
        elif len(num) > 1:
            if num[0] == '0':
                return False

        if int(num) > 255:
            return False
        return True

Reference

1. https://leetcode.com/problems/restore-ip-addresses/