AC python code, easy-understanding, follow the backtracking code template


  • 1
    D
        def restoreIpAddresses(self, s):
            ret = []
            self.dfs(ret, s, [], 0, 0)
            return ret
            
        def dfs(self, ret, s, path, index, depth):
            if depth == 4 and index == len(s):
                ret.append('.'.join(path))
                return ret
            if index >= len(s) or depth >= 4:
                return
            for i in range(index, max(index+3,len(s))):
                t = s[index:i+1]
                if t[0] == '0' and t != '0':
                    continue
                if 255 >= int(t) >= 0:
                    self.dfs(ret, s, path+[t], i+1, depth+1)
            
    

  • 0
    C

    Good solution. BTW, what do you mean by "follow the backtracking code template"?


  • 0
    H

    Yes would like to know the template as well


  • 0
    H

    Also you don't need depth

    class Solution(object):
        def dfs(self, ans, s, chosen, left):
            if (len(chosen) == 4 and left == len(s)):
                ans.append('.'.join(chosen))
            elif len(chosen) < 4:
                for right in range(left, min(left+3, len(s))):
                    choose = s[left:right+1]
                    if (int(choose) <= 255 and (len(choose) == 1 or choose[0] != '0')):
                        self.dfs(ans, s, chosen + [choose], right+1)
                        
        def restoreIpAddresses(self, s):
            ans = []
            chosen = []
            self.dfs(ans, s, chosen, 0)
            return ans

Log in to reply
 

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