Backtracking solution in Python


  • 0
    Y

    Just used the basic idea of solving combinations problems.

    class Solution(object):
        def restoreIpAddresses(self, s):
            """
            :type s: str
            :rtype: List[str]
            """
            def backtrack(path, res, start, count, s):
                if count==4:
                    if s=='':
                        tmpres = '.'.join(path[:])
                        if len(path)==4 and tmpres not in res: res.append(tmpres[:])
                else:
                    for l in [1,2,3]:
                        tmps = s[:l]
                        if tmps=='' or str(int(tmps))!=tmps: continue
                        if int(tmps)<0 or int(tmps)>255: continue
                        backtrack(path + [tmps], res, l, count + 1, s[l:])
            res = []
            backtrack([], res, 0, 0, s)
            return res
    

Log in to reply
 

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