AC Concise Python Solution with Explanation


  • 0
    Z

    The idea is simple: break down the string into 4 segments with each at least 1 digit and at most 3 digits, and check if all segments are valid. The isValidSegment( ) function checks if the number is between 0 and 255 with no leading 0, and if the number is 0, the original string must be '0' only.

    def restoreIpAddresses(self, A):
        def isValidSegment(string):
            num = int(string)
            return (0 < num <= 255 and string[0] != '0') \
            or (len(string) ==1 and num == 0)
    
        res = []
        n = len(A)
    
        for i in range(1, min(1 + 3,n)):
            for j in range(i + 1, min(i + 1 + 3, n)):
                for k in range(j + 1, min(j + 1 + 3, n)):
                     #if there are more than 3 digits for the last segment
                     #it must be wrong
                    if k < n - 3:
                        continue
                    segments = [A[:i], A[i:j], A[j:k], A[k:]]
                    if all(map(isValidSegment, segments)):
                        res.append('.'.join(segments))
        return res

Log in to reply
 

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