Python Solution(Beat over 99.5%) Boundary Analysis


  • 0
    J
    def restoreIpAddresses(self, s):
            """
            :type s: str
            :rtype: List[str]
            """
            if(not s):
                return []
            length = len(s)
            if(length < 4 ):
                return []
            res = []
            for i in xrange(max(1, length - 9), min(4, length - 2)):
                x1 = s[:i]
                if(i == 3 and int(x1) > 255):
                    break
                for j in xrange(max(1, length - (6 + i)), min(4, length - (1 + i))):
                    low = i + j
                    x2 = s[i:low]
                    if(j == 3 and int(x2) > 255):
                        break
                    for p in xrange(max(1, length - (3 + low)), min(4, length - low)):
                        high = low + p
                        x3 = s[low: high]
                        if(p == 3 and int(x3) > 255):
                            break
                        x4 = s[high:]
                        if(int(x4) > 255 or (len(x4) > 1 and x4[0] == '0')):
                            if(x3[0] == '0'):
                                break
                            else:
                                continue
                        res.append('.'.join([x1, x2, x3, x4]))
                        if(x3[0] == '0'):
                            break
                    if(x2[0] == '0'):
                        break
                if(x1[0] == '0'):
                    break
            return res  
    

    Of course u can use 4 loops with each from 1 to 3 and check their validity in the inner loop. but there is no need to enumerate them since the intrinsic constrain determines every range of each loop.
    With optimal "if else" checks to break the loop early and some code motion techniques to optimize the code. this python solution beat over 99.5%


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.