Python Backtracking, 99%


  • 0
    Y
    def restoreIpAddresses(self, s):
           
        if not s:
            return []
         
        result = [] 
        def dfs(stack, str):
            if len(stack) == 3 and int(str) < 256 and not (str[0] == '0' and len(str) > 1):
                result.append(stack + [str])
            else:
                
                if len(stack) < 3:
                    for i in xrange(len(str)-1):
                        num = int(str[0:i+1])
                        if num > 255: break                
                        if i > 0 and str[0] == '0': break
                        dfs(stack + [str[0:i+1]], str[i+1:])
            
    
        dfs([], s)
        return ['.'.join(ss) for ss in result]

Log in to reply
 

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