0.总结

• 本题实现起来还是有些麻烦的，建议20min

1. 题目

2. 分析

递归+细节实现。
主要就是找三个位置插入“.”号，在找点的时候，需要判断一下两个点得到的这个值是否合理（是否在[0,255]区间内，是否有前导0？）

3. 代码

class Solution:
    def __init__(self):
        self.res = []

    def restoreIpAddresses(self, s: str) -> List[str]:
        n = len(s)
        # num=3 表示有3次机会；
        # pos=0开始挑点
        self.dfs(s,3,0,n,[])
        return self.res
    
    # 需要记录分割点，最后保存结果
    def dfs(self,s,num,pos,n,arr):
        if num: # 如果还有插入的机会
            tmp = 0
            for i in range(pos,n):
                print(s[i])
                tmp = tmp*10 + int(s[i])
                if tmp>=0 and tmp <=255:
                    arr.append(i) # 在第i个字符后面分割开
                    self.dfs(s,num-1,i+1,n,arr)
                    arr.pop() # 删除这一个
        else: # 说明没有机会了
            if pos == n: # 如果到头儿了
                return             
            # 判断是否合理，主要是pos~n 的值
            tmp = 0
            while(pos<n and tmp <= 255):
                tmp = tmp*10 + int(s[pos])
                pos+=1
            if pos == n and tmp <= 255: # 需要找出所有结果
                cur = []
                # 不能有前导0
                if (s[0:arr[0]+1].startswith("0") and len(s[0:arr[0]+1])>1 
                or (s[arr[0]+1:arr[1]+1].startswith("0") and len(s[arr[0]+1:arr[1]+1])>1)
                or (s[arr[1]+1:arr[2]+1].startswith("0") and len(s[arr[1]+1:arr[2]+1])>1)
                or (s[arr[2]+1:].startswith("0") and len(s[arr[2]+1:]) > 1)
                ):
                    return
                cur.append(s[0:arr[0]+1])
                cur.append(s[arr[0]+1:arr[1]+1])
                cur.append(s[arr[1]+1:arr[2]+1])
                cur.append(s[arr[2]+1:])
                print(cur)
                for i in arr: # 遍历所有的可能值                                
                    print(i,end= ",")
                print("\n")
                self.res.append(".".join(cur))
                # self.res +=1