Easy to read python backtracking solution 50ms


  • 0
    J
    class Solution(object):
        def valid(self, s):                                                                  
            if int(s) > 255:
                return False                                                                 
                                                                                             
            # Rejects things like 001.x  01.x                                                
            if s[0] == '0' and not len(s) == 1:                                              
                return False                                                                 
            
            return True 
                
        def restoreIpAddresses(self, s, start=0, depth=1):                                   
            if depth > 4:
                return False
                    
            # Leaf level of the recursion tree.
            if depth == 4:
                remString = s[start:]                                                        
            
                if len(remString) > 3 or not self.valid(remString):                          
                    return False                                                             
                else:
                    return [remString]
                
            results = []                                                                     
            for i in [1, 2, 3]:                                                              
                # Skip if out of bounds or invalid
                if start + i > (len(s) - 1) or not self.valid(s[start:start+i]):             
                    continue                                                                 
                                                                                             
                suffixes = self.restoreIpAddresses(s, start+i, depth+1)                      
                if suffixes:
                    for suffix in suffixes:                                                  
                        results.append("%s.%s" % (s[start:start+i], suffix))                 
                
            return results

Log in to reply
 

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