题解 | 数字字符串转化成IP地址-******** lcr 087

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @return string字符串一维数组
#
class Solution:
    def restoreIpAddresses(self , s: str) -> List[str]:
        # write code here
        res=[]
        segements=[]
        slen=len(s)
        def  backtrack(s,start:int ,segements:list ,res:list):
            k=len(segements)
            if k==4 and start==slen:
                #print("add",segements)
                res.append(segements[0]+"."+segements[1]+"."+segements[2]+"."+segements[3])
                return
            # 剪枝
            if k>4 or start>=slen:
                return 
            # # 剪枝   // 剪枝：剩余的字符数必须满足 [4-k, 3*(4-k)] 区间
            # remaing=slen-k #剩余长度
            # # if  remaing<4-k or remaing> 3*(4-k):
            # #     return
            

            # 遍历每段3中情况，即三种长度 ： 1， 11,111
            for end in range(1,4):
                
                sub_str=s[start:start+end]
                #print(sub_str)
                #剪枝 有前导0 或者超出255
                
                if (len(sub_str)>1 and sub_str[0]=='0') or int(sub_str)>255:
                    break
            
                segements.append(sub_str)
                backtrack(s,start+end,segements,res)
                segements.pop()
        backtrack(s,0,segements,res)
        return res