java复原IP 地址（力扣Leetcode93）

复原IP 地址

力扣原题链接

问题描述

有效 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

例如：“0.1.2.201” 和 “192.168.1.1” 是有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是无效 IP 地址。

给定一个只包含数字的字符串 s，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ‘.’ 来形成。不能重新排序或删除 s 中的任何数字。可以按 任何 顺序返回答案。

示例

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

解题思路

这是一个回溯算法的经典问题，我们需要通过在字符串 s 中插入点来形成有效的 IP 地址。有效的 IP 地址由四个整数组成，每个整数位于 0 到 255 之间，且不能含有前导 0。

我们可以使用回溯算法来尝试所有可能的分割方案，并验证每个分割是否满足 IP 地址的要求。

1. 回溯搜索： 定义一个回溯函数 backtrack，其参数包括当前处理的索引 start、当前的字符串 s、当前已形成的 IP 地址列表 path 和当前已形成的 IP 地址段数量 segments。
2. 结束条件： 如果已形成的 IP 地址段数量 segments 等于 4 且 start 等于字符串 s 的长度，说明已经形成了一个有效的 IP 地址，将其加入结果列表，并返回。
3. 选择列表： 在当前索引 start 后插入一个点，形成新的 IP 地址段。
4. 遍历选择： 遍历从当前索引 start 开始的所有可能的分割点，尝试形成新的 IP 地址段。
5. 判断是否合法： 对于每个可能的分割点，检查其所形成的 IP 地址段是否合法，即是否满足整数在 0 到 255 之间，且不能含有前导 0。
6. 递归进入下一层： 如果形成的 IP 地址段合法，则将其加入当前 IP 地址列表，并递归调用回溯函数，传入新的索引 i + 1、更新后的 IP 地址列表和 IP 地址段数量。
7. 撤销选择： 回溯到上一层时，将刚刚加入的 IP 地址段从列表中删除，继续尝试下一个分割点。
   

Java解题

import java.util.*;class Solution {List<String> res = new ArrayList<>();public List<String> restoreIpAddresses(String s) {List<String> path = new ArrayList<>();backtrack(s, 0, path, 0);return res;}public void backtrack(String s, int start, List<String> path, int segments) {// 结束条件：已形成 4 个 IP 地址段，并且已遍历完整个字符串if (segments == 4 && start == s.length()) {res.add(String.join(".", path));return;}// 遍历可能的分割点for (int i = start; i < s.length(); i++) {String seg = s.substring(start, i + 1);// 判断 IP 地址段是否合法if (isValidSegment(seg)) {// 做出选择path.add(seg);// 递归进入下一层backtrack(s, i + 1, path, segments + 1);// 撤销选择path.remove(path.size() - 1);} else {// 如果当前分割点不合法，不必继续尝试更长的 IP 地址段break;}}}// 判断 IP 地址段是否合法private boolean isValidSegment(String segment) {if (segment.length() > 1 && segment.charAt(0) == '0') {return false; // IP 地址段不能含有前导 0}int num = Integer.parseInt(segment);return num >= 0 && num <= 255;}
}

通过回溯算法，我们可以找出给定字符串 s 的所有可能的有效 IP 地址组合。在回溯搜索的过程中，我们使用了剪枝操作来提高算法的效率，避免不必要的递归。