边工作边刷题：70天一遍leetcode: day 20-3

Restore IP Addresses

要点：典型的backtrack的题，但是不同的是有一些限制条件可以剪枝。

• start>=n是中止条件，而层数是成功条件
• 因为要计算剩余位的长度来剪枝，所以层数在递归中应该是递减的。这样条件就是个数在层数3和层数1之间。
• 1位，2位，3位写成三个并行的情况，每个都进一步dfs

错误点：

• 不论是2位还是3位，只要检查leading不是0即可，比如001，检查leading 0就可以了，其他位不是检查条件。
• 3位要检查不能超过255
• 注意长度的计算：n不是最后的index，所以长度为n-start

class Solution(object):
    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        def dfs(start, s, kth, res, solutions):
            n = len(s)
            if start>=n:
                if kth==0:
                    resCp = list(res)
                    solutions.append('.'.join(resCp))
                return
            
            if n-start>kth*3 or n-start<kth*1:
                return
            
            # 1
            cur = s[start:start+1]
            print cur
            res.append(cur)
            dfs(start+1, s, kth-1, res, solutions)
            res.pop()
            
            # 2
            if s[start]!='0' and start+1<n:
                cur = s[start:start+2]
                print cur
                res.append(cur)
                dfs(start+2, s, kth-1, res, solutions)
                res.pop()
            
            # 3
            if start+2<n and s[start]!='0':
                cur = s[start:start+3]
                print cur
                if int(cur)<=255:
                    res.append(cur)
                    dfs(start+3, s, kth-1, res, solutions)
                    res.pop()
        
        solutions = []    
        res = []
        dfs(0, s, 4, res, solutions)
        return solutions