题目描述
有效 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：这题其实是“回溯剪枝能力”的入门经典题，比单纯组合题更接近真实复杂问题，多刷几遍会很有感觉 🚀