前往此题

解题思路

回溯算法

根据IP地址的特性我们可以总结出以下几点：

1. 字符串长度不能小于4且不能大于12
2. 每个IP段的取值范围在0~255之间
3. IP段不能存在前导0，如果遇到0则说明此IP段必为0

已知了这三个特点首先想到的就是回溯算法。

算法过程

1. 遍历整个字符串，对每个IP段检查其可能性。
2. 创建segments来存储可能是有效IP的字符串，初始化为[0,0,0,0]，创建res为最终结果
3. 如果遇到为0, 由于不存在前导0的情况，将0存入segments
4. 存入的IP段必须符合0~255之间
5. 如果存入了4个IP段之后，还没有完全遍历完str,说明字符串str不是合法的IP地址直接返回即可

代码

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        
        SEG_COUNT = 4
        res = list()
        segments = [0] * SEG_COUNT

        def dfs(segId: int, segStart: int):
            if segId == SEG_COUNT:
                if segStart == len(s):
                    address = '.'.join(str(seg) for seg in segments)
                    res.append(address)
                return
            if segStart == len(s): return 

            if s[segStart] == '0':
                segments[segId] = 0
                dfs(segId + 1, segStart + 1)
            
            addr = 0
            for end in range(segStart, len(s)):
                addr = addr * 10 + (ord(s[end]) - ord('0'))
                if 0 < addr <= 255:
                    segments[segId] = addr
                    dfs(segId + 1,   + 1)
                else: break
        dfs(0, 0)
        return res