【leetcode】93. 复原IP地址

题目

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

示例:

输入: “25525511135”

输出: [“255.255.11.135”, “255.255.111.35”]

解题思路

ip地址分为四节，每节取值范围在[0,255]

对于取出的字符串，若它的第一位为’0’，那么它的长度只能为1，多位字符不能以0作为开头

每次拿出[1,3]个字符，判断是否符合ip地址的条件，若符合，则递归剩下的字符串，直到四节都符合，那么就得到了一个解

def isTrue(s):
    #首先判断是否以0开头
    if s.find("0")==0:
        if len(s)>=2:
            return False
        else:
            return True
    else:
        if int(s)>255:
            return False
        else:
            return True

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        s_len=len(s)
        if s_len>12 or s_len==0:
            return []
        def solve(s,k):
            # k 目前已经找到几个了
            res=[]
            if k==3:
                if len(s)>3 or len(s)==0 or isTrue(s)==False:
                    return []
                else:
                    return [[s]]
            else:
                for i,c in enumerate(s):
                    if i>=3:
                        break
                    if isTrue(s[0:i+1]):                        
                        for tmp in solve(s[i+1:],k+1):
                            head_l=[s[0:i+1]]
                            head_l.extend(tmp)
                            res.append(head_l)
                    else:
                        break
            return res
        res=[".".join(a) for a in solve(s,0)]
        return res