Python Simple Backtrack Solution


  • 0
    D
    class Solution(object):
        def restoreIpAddresses(self, s):
            """
            :type s: str
            :rtype: List[str]
            """
            ans = []
            def collect(remain, curr):
                if len(curr) == 4:
                    if remain == 0: ans.append('.'.join(reversed(curr)))
                    return
                for k in range(1, min(3, remain)+1):
                    first = s[remain-k:remain]
                    if (k == 1 or first[0]!= '0') and int(first)<=255:
                        collect(remain - k, curr + [first])
            collect(len(s), [])
            return ans

Log in to reply
 

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