Backtracking in Python


  • 0
    class Solution(object):
        ipss = []
        def restoreIpAddresses(self, s):
            self.ipss = []
            self.helper(s,"",0)
            return self.ipss
    
        def helper(self, s, ip, level):
            """
            :type s: str
            :rtype: List[str]
            """
            if level == 4:  
                if len(s) == 0:
                    ip = ip[1:]
                    self.ipss.append(ip)
                return
            for x in range(1,4):
                if len(s[:x]) != x:
                    break #continue
                if self.ValidIp(s[:x]):
                        self.helper(s[x:],ip + "." + s[:x], level+1)
            
        def ValidIp(self,s):
            if len(s) < 1 or len(s) >3:
                return False
            if int(s) < 0 or int(s) >255:
                return False
            if len(str(int(s))) != len(s):
                return False
            return True
    
    solver = Solution()
    print solver.restoreIpAddresses("0000") 
    print solver.restoreIpAddresses("1111")
    

Log in to reply
 

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