- 正确答案：该题要求将一个只包含数字的字符串恢复为所有可能的有效IP地址。有效IP地址由4个整数（0~255）组成，用3个点分隔，且每个整数不能有前导零（除非该整数本身就是0）。解法采用回溯（DFS）枚举所有合法的三段分割位置，对每种分割验证每一段是否符合IP段规则。最终返回所有合法组合。 - 解答思路： 1. IP地址必须恰好分为4段，因此需要在字符串中插入3个分隔点，等价于选择3个分割位置（即确定4个子串的起始和结束索引）。 2. 使用回溯递归：维护当前已划分的段数 path（List），以及下一个待处理字符的起始下标 start。 3. 每层递归尝试从 start 开始取长度为1、2、3的子串（因为单段最长为3位数，对应255），判断该子串是否为合法IP段： - 长度 > 1 时不能以 '0' 开头（排除"01", "00"等）； - 数值范围必须在 [0, 255] 内（注意：字符串转整数可能溢出，但题目保证输入仅含数字，且长度≤12，故可安全转换；更稳妥做法是逐字符校验或限制长度后直接比字符串："255" >= s >= "0"，但需注意"0"合法、"00"非法）； 4. 若已划分4段且耗尽整个字符串（start == s.length()），则找到一个解，加入结果集； 5. 若段数已达4但未耗尽字符串，或未达4段但已越界，则剪枝； 6. 回溯：每次尝试后，将子串加入path，递归处理下一段；返回后移除该子串（撤销选择）。 - 深度知识讲解：本题本质是「组合型回溯」问题，核心考察：（1）**回溯框架的建模能力**：如何将“切分位置”转化为状态空间树——每个节点代表当前已确定的若干段，分支代表下一段的可能长度（1/2/3）。树深固定为4，每层分支至多3种选择，总时间复杂度上界为 O(3^4) = 81，实际因剪枝更低。（2）**合法性校验的底层细节**： • 前导零判定：不能简单用 Integer.parseInt(s) != 0 判断，因为 "0" 合法而 "00" 非法。正确方式是：若子串长度 > 1 且 s.charAt(0) == '0' → 非法； • 数值范围校验：避免 parseInt 导致的异常或溢出（虽然本题无负号且长度受限），推荐先判长度：若 len > 3 → 必非法；若 len == 3，则只需比较字符串是否 <= "255"（字典序比较成立，因等长且全数字）；更通用做法是遍历计算数值，边算边判断是否 > 255（防溢出）： int num = 0; for (int i = start; i < end; i++) { num = num * 10 + (s.charAt(i) - '0'); if (num > 255) return false; // 提前终止 } （3）**剪枝优化策略**： • 剩余字符数不足：若剩余字符数 < (4 - path.size()) → 不够分完4段，剪枝； • 剩余字符数过多：若剩余字符数 > 3 * (4 - path.size()) → 某段必超3位，剪枝；这两个剪枝可在进入递归前快速过滤无效分支，显著提升效率。（4）**与经典回溯题的区别**：本题不是从数组选元素，而是对字符串做「区间划分」，状态变量是下标而非索引集合，属于「分割类回溯」典型范式（类似 LeetCode 131. 分割回文串）。 - 代码示例（Java，含详细注释和剪枝）： ``` public List restoreIpAddresses(String s) { List res = new ArrayList<>(); backtrack(s, 0, new ArrayList<>(), res); return res; } private void backtrack(String s, int start, List path, List res) { // 终止条件：已划分4段 if (path.size() == 4) { if (start == s.length()) { res.add(String.join(".", path)); } return; } // 剪枝1：剩余字符不够分给剩下段数（每段至少1字符） int remainingSegments = 4 - path.size(); if (s.length() - start < remainingSegments) return; // 剪枝2：剩余字符太多，超过剩下段数*3（每段最多3字符） if (s.length() - start > remainingSegments * 3) return; // 尝试取长度为1/2/3的子串作为当前段 for (int len = 1; len <= 3 && start + len <= s.length(); len++) { String segment = s.substring(start, start + len); // 合法性检查：前导零 & 数值范围 if (segment.length() > 1 && segment.charAt(0) == '0') continue; // 前导零非法 if (len == 3) { // 三位数必须 <= 255：直接字符串比较（等长数字字典序=数值序） if (segment.compareTo("255") > 0) continue; } // 递归：加入当前段，处理后续 path.add(segment); backtrack(s, start + len, path, res); path.remove(path.size() - 1); // 回溯撤销 } } ``` - 扩展知识： • 该算法可推广至任意k段分割问题（如恢复IPv6需8段十六进制，但规则不同）； • 在网络协议栈实现中，IP地址解析常使用有限状态机（FSM）进行O(n)线性校验，而本题是生成所有可能——体现「验证」vs「生成」两类问题的差异； • 若要求返回字典序最小解（而非全部），可用贪心+验证：优先取最短合法段（如"1"而非"12"），但本题需穷举，故回溯不可替代； • 实际工业级IP校验库（如Apache Commons Validator）会严格遵循RFC 3986，支持IPv4/IPv6混合、CIDR掩码等，但本题仅考察基础字符串分割逻辑。

字节生活服务后端日常实习二面

全站热榜

创作者周榜