Python 45ms


  • 0
    E

    Idea is to try permutations of blocks with up to 3 characters each.

        def permuter(self, depth, i, st, seq, res):
            # check if a valid IP address can be made with the rest of the string
            if i >= len(st) or (5-depth)*3 < len(st)-i: return
            if depth == 4: # last block
                s = st[i:]
                if len(st)-i > 1 and st[i] == '0' or int(s) > 255: return
                res.add(''.join(seq) + s)
            else:
                for r in range(1, min(4,len(st)-i)): # try for next 3 char or 1 less than end of string
                    s = st[i:i+r]
                    if r > 1 and st[i] == '0' or int(s) > 255: continue
                    seq.append(s + ".")
                    self.permuter(depth+1, i+r, st, seq, res)
                    seq.pop()
        
        def restoreIpAddresses(self, s):
            """
            :type s: str
            :rtype: List[str]
            """
            if len(s) < 4: return []
            res = set()
            self.permuter(1, 0, s, [], res)
            return list(res)
    

Log in to reply
 

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