Python standard backtracking easy to understand


  • 0
    W

    '''

    def restoreIpAddresses(self, s):
        ret = []
        self.dfs(s, 0, '', ret)
        return ret
    
    def dfs(self, s, index, cur, ret):
        if cur.count('.') > 3: return
        elif cur.count('.') == 3:
            if index >= len(s):
                ret.append(cur)
            return
        for i in range(index, min(index+3, len(s))):
            check = s[index:i+1]
            toAdd = check if not cur else '.' + check
            cur += toAdd
            if (check[0] != '0' and 0 < int(check) <= 255) or check == '0':
                self.dfs(s, i+1, cur, ret)    
            cur = cur[:len(cur)-len(toAdd)]
    

    '''


Log in to reply
 

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