Hexo

2020-08-15

##思路

res List[str]：记录当前已被分隔的字符串，初始值为 [s]，未做分隔
for 循环 3 次，每次给 res 中所有字符串加一个 ‘.’，多分隔出一个整数，例如 [“2552551135”] 一次循环之后，变成 [“2.552551135”, “25.52551135”, “255.2551135”]，分隔出了一个合法整数
然后在最后面的那串又加 ‘.’，继续分隔，维护好加 ‘.’ 分隔的位置
添加三个 ‘.’ 后，分隔出的前三个整数都已满足条件，只需检验一下分隔出的最后一个整数即可，若满足条件，则四个整数都满足条件

##代码

class Solution:
    def validInt(self, s):
        if s and int(s) < 256:
            if s[0] != '0' or s == '0':
                return True
        return False
def restoreIpAddresses(self, s: str):
    res = [s]
    for _ in range(3):
        res_now = []
        for si in res:
            last = si.split('.')[-1]
            idx = len(si) - len(last)
            for i in range(len(last)):
                if i > 2:
                    break
                if int(last[:i + 1]) < 256:
                    si_now = si[: idx + i + 1] + '.' + si[idx + i + 1 :]
                    res_now.append(si_now)
                if last[0] == '0':
                    break
        res = res_now

    res_now = []
    for si in res:
        last = si.split('.')[-1]
        if self.validInt(last):
            res_now.append(si)

    return res_now