LeetCode - 93.复原IP地址

题目描述

有效 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任意顺序返回答案。

思路

本题是典型的回溯问题，核心就是：切割字符串 + 剪枝判断合法性。整体思路：

使用回溯（DFS）枚举所有切割方式
每次切一段（长度 1~3）
判断当前段是否合法
递归继续切下一段
当切成 4 段且刚好用完所有字符时，加入结果

涉及方法

1. 回溯模板（切割问题）

const res = []
const path = []
 
function backtrack(startIndex){
    if(终止条件){
        res.push(path.join('.'))
        return
    }
 
    for(let i = startIndex; i < s.length; i++){
        // 做选择
        path.push(当前切割)
 
        backtrack(i + 1)
 
        // 撤销选择
        path.pop()
    }
}

2. 剪枝（合法性判断）

IP 地址每一段需要满足：

数值在 0 ~ 255
不能有前导 0（例如 "01" 不合法）
长度最多 3 位

function isValid(s, start, end){
    if(start > end) return false
 
    // 前导 0
    if(s[start] === '0' && start !== end) return false
 
    let num = 0
    for(let i = start; i <= end; i++){
        num = num * 10 + (s[i] - '0')
        if(num > 255) return false
    }
 
    return true
}

3. 回溯过程

var restoreIpAddresses = function(s) {
    const res = []
    const path = []
 
    function backtrack(startIndex){
        // 如果已经切了4段
        if(path.length === 4){
            // 同时用完所有字符
            if(startIndex === s.length){
                res.push(path.join('.'))
            }
            return
        }
 
        for(let i = startIndex; i < s.length; i++){
            // 剪枝
            if(!isValid(s, startIndex, i)) break
 
            let str = s.slice(startIndex, i + 1)
            path.push(str)
 
            backtrack(i + 1)
 
            path.pop()
        }
    }
 
    backtrack(0)
    return res
};

实际处理

剪枝优化非常关键

如果当前段已经不合法，其实后面更长的一定也不合法（因为数值只会更大）

这个优化能明显减少递归次数。

4. 切割问题的本质理解

这题本质就是： “在字符串中找切割点”

和这些题是同一类：

分割回文串
组合问题（选 or 不选）
子集问题

总结

这题可以总结为一句话： 回溯 = 切割 + 校验 + 剪枝 关键点就三个：

切几段（path.length 控制）
合不合法（isValid）
提前停止（break 剪枝）

ps：这题其实是“回溯剪枝能力”的入门经典题，比单纯组合题更接近真实复杂问题，多刷几遍会很有感觉 🚀