My python code using backtracking recipe of Skiena


  • 0
    P
        def restoreIpAddresses(self, s):
            """
            :type s: str
            :rtype: List[str]
            """
            def is_solution(a, k, n, s, sols):
                # dotted decimal notations will have 4 numbers
                # entire string has been consumed
                return k == 4 and n == len(s)
            
            
            def process_solution(a, k, n, s, sols):
                # prepare dotted decimal notations
                sols.append('.'.join(a))
            
            
            def construct_candidates(a, k, n, s, sols):
                candidates = []
            
                if len(s) >= 3 and int(s[:3]) <= 255  and s[:3][0] != '0': # ignore with preceeding 0, numbers > 255
                    candidates.append(s[:3])
                if len(s) >= 2 and int(s[:2]) <= 255  and s[:2][0] != '0': # ignore with preceeding 0, numbers > 255
                    candidates.append(s[:2])
                if len(s) >= 1 and int(s[:1]) <= 255: # can't strip off preceeding 0 if there is only one digit
                    candidates.append(s[:1])
            
            
                return candidates
            
            
            def backtrack(a, k, n, s, sols):
                if is_solution(a, k, n, s, sols):
                    process_solution(a, k, n, s, sols)
                else:
                    candidates = construct_candidates(a, k, n, s[n:], sols)
                    k = k + 1
                    for candidate in candidates:
                        a.append(candidate)
                        n = sum(map(len,a))
                        backtrack(a, k, n, s, sols)
                        a.pop()
    
            if len(s) > 12:
                return []
            
            a = []
            k = 0
            sols = []
            backtrack(a,k,0,s,sols)
            return sols

Log in to reply
 

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