leetcode 93 复原IP地址

通过递归，当满足了4层递归树，以及遍历元素到达字符串尾部（意味着用完了字符串中的数据）则可以把结果装入最终数组中，通过".".join()，如果没有满足层数，但是到达了数组尾部，那么也应该返回
然后如果当前字符为“0”那就特殊处理下
在递归的过程中，可以把数*10加和获得一个数字，然后判断是否在0与255之间（包括255)，然后继续递归，不满足则break剪枝。

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        def dfs(j,t,result,allresult):           

            if t==4:
                if j == len(s):
                    print(result[:])
                    allresult.append(".".join(result[:]))
                return
            if j == len(s):
                print(result)
                return  

            if s[j]=="0":

                dfs(j+1,t+1,result+["0"],allresult)


            addr=0
            for i in range(j,len(s)):

                addr=addr*10+(ord(s[i])-ord("0"))

                if 0<addr<=0xFF:

                    dfs(i+1,t+1,result+[str(addr)],allresult)
                else:
                    break


        if len(s)==0:
            return []
        allresult=[]
        result=[]
        dfs(0,0,result,allresult)
        return allresult

自己的方法 不用循环，或循环变量设置为range(0,3),这里的判断剩下的元素是否过多或者不够用剪枝条件需要想清楚一点。

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:

        def check(s):
            s=int(s)

            if s<=255 and s>0:
                return True


        def dfs(j,t,result,allresult):

            if t==4:
                if j==len(s):
                    allresult.append(".".join(result))
                return 
            if j==len(s):
                return 
            if s[j]=='0':

                dfs(j+1,t+1,result+[s[j]],allresult)

            if len(s)-j>(4-t)*3 or len(s)-j<(4-t):
                return 

            else:
                if ord(s[j])-ord('0') not in [1,2,3,4,5,6,7,8,9]:return 

                if j<len(s) and check(s[j]):
                    #print(s[j])
                    dfs(j+1,t+1,result+[s[j]],allresult)
                if j+2<=len(s) and check(s[j:j+2]):
                    print(s[j:j+2])
                    dfs(j+2,t+1,result+[s[j:j+2]],allresult)
                if j+3<=len(s) and check(s[j:j+3]):
                    print(s[j:j+3])
                    dfs(j+3,t+1,result+[s[j:j+3]],allresult)


        if len(s)==0:
            return []
        allresult=[]
        result=[]
        dfs(0,0,result,allresult)
        return allresult