Python DFS Solution w/ Comments


  • 0
    class Solution(object):
        def restoreIpAddresses(self, s):
            res = []
            self.dfs(s, "", 0, res)
            return res
            
        def dfs(self, s, path, parts, res):
            # need to have 4 parts
            if not s and path and parts == 4:
                res.append(path)
            elif parts < 4:
                for i in range(1, min(len(s)+1, 4)):
                    ip_part = s[0:i]
                    # if starts with 0 but not 0 or outside range of IP continue
                    if not ip_part or ip_part[0] == '0' and len(ip_part) > 1 or int(ip_part) < 0 or int(ip_part) > 255:
                        continue
                    # start up IP path
                    if not path:
                        self.dfs(s[i:], ip_part, parts+1, res)
                    # continue IP Path
                    else:
                        self.dfs(s[i:], path+'.'+ip_part, parts+1, res)
    

    Criteria for IP: need to be between 0 and 255, and must have 4 parts


Log in to reply
 

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