93. 复原IP地址

https://leetcode-cn.com/problems/restore-ip-addresses/

解法一：

dfs遍历，每层递归尝试截取1~3位（每段ip位数为1~3），为防止递归栈过深，递归出口设为4段（ip只有4段）。

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        self.res = []
        tmpList = []
        self.dfs(s, tmpList)
        return self.res

    #dfs遍历，s为待处理字段，tmp存储所有ip小段
    def dfs(self, s, tmpList):  
        if len(tmpList) == 4:   #递归出口，凑够4段
            if len(s) == 0:     #s没有剩余，说明找到一个合法ip，否则返回
                self.res.append('.'.join(tmpList))
            return      
        for i in range(1, 4):   #遍历取s的头，长度从1到3
            if i <= len(s):     #防止越界
                if int(s[:i]) > 255:    #数字超出范围
                    return
                elif i > 1 and s[0] == '0':    #除去0开头，且长度大于1情况
                    return
                self.dfs(s[i:], tmpList + [s[:i]])  #截断s，并将本次截取内容写入tmp