CodeTop 代码随想录 Q75.复原IP地址

思路：这道题同上一道题Q74.分割回文串类似，都是切割问题。切割问题可以使用回溯搜索法把所有的可能性搜索出来。将该切割问题抽象为树形结构如下图所示：

回溯三部曲：

1.确定递归参数：切割问题类似于组合问题。

（1）原始字符串s。

（2）还需要startIndex记录下一层递归分割的起始位置（不能重复分割）。

（3）还需要一个变量pointNum记录添加小数点的数量。

List<String> res = new ArrayList<>(); StringBuilder sb = new StringBuilder();

public void backTracking(String s,int startIndex,int num)

2.确定递归终止条件：与Q74.分割回文串不同，本题明确要求只会分成4段，所以不能用切割线切到最后作为终止条件，而是分割的段数作为终止条件。num表示ip段的数量。当ip段的数量为4且切割线走到最后时，终止。

if(startIndex == s.length() && num == 4){ res.add(sb.toString()); return; }

3.确定单层搜索的逻辑：在循环遍历中截取子串的方法同Q74.分割回文串。在for (int i = startIndex; i < s.size(); i++)循环中[startIndex, i] 这个区间就是截取的子串，需要判断这个子串是否合法。如果合法就在字符串后面加上“.”符号表示已经分割。如果不合法就结束本层循环，如图中剪掉的分支。

4.然后是递归和回溯的过程：递归调用时，下一层递归的startIndex要从i+2开始（因为需要在字符串中加入分割符“.”），同时记录分隔符的数量pointNum要＋1。回溯的时候将刚刚加入的分隔符“.”删掉，pointNum也要-1。

5.最后要判断子串是否合法：判断每个整数段是否为有效整数段，主要考虑以下三点（2和3用于确定for循环区间）。

（1）整数段以0为开头的数字不合法。

（2）整数段里有非正整数字符的不合法。

（3）整数段如果大于255了不合法。

Integer.parseInt()方法：将字符串参数解析为有符号的十进制整数。

字符串的substring()方法和stringbuilder.delete()方法都是前闭后开区间。

//如果二者仅满足其一，则直接返回 if(startIndex == s.length() || num == 4){ return; } //Integer.parseInt方法：将字符串参数解析为有符号的十进制整数。 for(int i = startIndex;i < s.length() && i - startIndex < 3 && Integer.parseInt(s.substring(startIndex,i+1)) >= 0 && Integer.parseInt(s.substring(startIndex,i + 1)) <= 255; i++){ if(i - startIndex > 0 && s.charAt(startIndex) - '0' == 0){ break; } sb.append(s.substring(startIndex,i + 1)); //如果sb里的ip段数量小于3，才会加点；如果等于3，说明已经有3段了，最后一段不需要再加点。 if(num < 3){ sb.append("."); } num ++; backTracking(s,i + 1,num); num --; //stringbuilder.delete()是前闭后开区间 //删除当前sb的最后一个ip段，同时删除后面跟着的小数点，因此要加1。 sb.delete(startIndex + num,i + num + 2); }

附代码：

class Solution { List<String> res = new ArrayList<>(); StringBuilder sb = new StringBuilder(); public List<String> restoreIpAddresses(String s) { backTracking(s,0,0); return res; } //num表示stringbuilder中ip段的数量 public void backTracking(String s,int startIndex,int num){ if(startIndex == s.length() && num == 4){ res.add(sb.toString()); return; } // 如果二者仅满足其一，则直接返回 // 说明已经用完了所有字符但是IP数还不够4段；或者已经凑够了四段但是还有字符没有用完 // 两种情况都表示这条路走不通，直接返回 if(startIndex == s.length() || num == 4){ return; } //Integer.parseInt方法：将字符串参数解析为有符号的十进制整数。 for(int i = startIndex;i < s.length() && i - startIndex < 3 && Integer.parseInt(s.substring(startIndex,i+1)) >= 0 && Integer.parseInt(s.substring(startIndex,i + 1)) <= 255; i++){ // 如果当前截取的IP段长度大于1，并且当前段的第一个字符是0，就跳出循环 // 防止出现前导0 if(i - startIndex > 0 && s.charAt(startIndex) - '0' == 0){ break; } sb.append(s.substring(startIndex,i + 1)); //如果sb里的ip段数量小于3，才会加点；如果等于3，说明已经有3段了，最后一段不需要再加点。 if(num < 3){ sb.append("."); } num ++; backTracking(s,i + 1,num); num --; //stringbuilder.delete()是前闭后开区间 //删除当前sb的最后一个ip段，同时删除后面跟着的小数点，因此要加1。 sb.delete(startIndex + num,i + num + 2); } } }

ACM模式：

import java.util.ArrayList; import java.util.List; import java.util.Scanner; class Solution { List<String> res = new ArrayList<>(); StringBuilder sb = new StringBuilder(); public List<String> restoreIpAddresses(String s) { backTracking(s, 0, 0); return res; } // num表示stringbuilder中ip段的数量 public void backTracking(String s, int startIndex, int num) { if (startIndex == s.length() && num == 4) { res.add(sb.toString()); return; } // 如果二者仅满足其一，则直接返回 if (startIndex == s.length() || num == 4) { return; } for (int i = startIndex; i < s.length() && i - startIndex < 3 && Integer.parseInt(s.substring(startIndex, i + 1)) >= 0 && Integer.parseInt(s.substring(startIndex, i + 1)) <= 255; i++) { if (i - startIndex > 0 && s.charAt(startIndex) - '0' == 0) { break; } sb.append(s.substring(startIndex, i + 1)); // 如果sb里的ip段数量小于3，才会加点；如果等于3，说明已经有3段了，最后一段不需要再加点。 if (num < 3) { sb.append("."); } num++; backTracking(s, i + 1, num); num--; // stringbuilder.delete()是前闭后开区间 // 删除当前sb的最后一个ip段，同时删除后面跟着的小数点，因此要加1。 sb.delete(startIndex + num, i + num + 2); } } } public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 读取字符串s String s = scanner.nextLine(); // 计算所有可能的IP地址 Solution solution = new Solution(); List<String> result = solution.restoreIpAddresses(s); // 输出结果，每个IP地址占一行 for (String ip : result) { System.out.println(ip); } scanner.close(); } }

构造测试用例：

import java.util.*; class Solution { List<String> res = new ArrayList<>(); StringBuilder sb = new StringBuilder(); public List<String> restoreIpAddresses(String s) { res.clear(); sb.setLength(0); backTracking(s, 0, 0); return res; } // num表示stringbuilder中ip段的数量 public void backTracking(String s, int startIndex, int num) { if (startIndex == s.length() && num == 4) { res.add(sb.toString()); return; } // 如果二者仅满足其一，则直接返回 if (startIndex == s.length() || num == 4) { return; } for (int i = startIndex; i < s.length() && i - startIndex < 3 && Integer.parseInt(s.substring(startIndex, i + 1)) >= 0 && Integer.parseInt(s.substring(startIndex, i + 1)) <= 255; i++) { if (i - startIndex > 0 && s.charAt(startIndex) - '0' == 0) { break; } sb.append(s.substring(startIndex, i + 1)); // 如果sb里的ip段数量小于3，才会加点；如果等于3，说明已经有3段了，最后一段不需要再加点。 if (num < 3) { sb.append("."); } num++; backTracking(s, i + 1, num); num--; // stringbuilder.delete()是前闭后开区间 // 删除当前sb的最后一个ip段，同时删除后面跟着的小数点，因此要加1。 sb.delete(startIndex + num, i + num + 2); } } } public class Main { // 手动构造测试用例 public static void main(String[] args) { Solution solution = new Solution(); // 测试用例1：基本情况 String s1 = "25525511135"; List<String> result1 = solution.restoreIpAddresses(s1); System.out.println("测试用例1 - 输入: \"" + s1 + "\""); System.out.println("所有可能的IP地址:"); for (String ip : result1) { System.out.println(" " + ip); } System.out.println("期望: [\"255.255.11.135\", \"255.255.111.35\"]"); System.out.println(); // 测试用例2：包含0的情况 String s2 = "0000"; List<String> result2 = solution.restoreIpAddresses(s2); System.out.println("测试用例2 - 输入: \"" + s2 + "\""); System.out.println("所有可能的IP地址:"); for (String ip : result2) { System.out.println(" " + ip); } System.out.println("期望: [\"0.0.0.0\"]"); System.out.println(); // 测试用例3：包含前导0的情况 String s3 = "010010"; List<String> result3 = solution.restoreIpAddresses(s3); System.out.println("测试用例3 - 输入: \"" + s3 + "\""); System.out.println("所有可能的IP地址:"); for (String ip : result3) { System.out.println(" " + ip); } System.out.println("期望: [\"0.10.0.10\", \"0.100.1.0\"]"); System.out.println(); // 测试用例4：数字长度刚好12位 String s4 = "123456789012"; List<String> result4 = solution.restoreIpAddresses(s4); System.out.println("测试用例4 - 输入: \"" + s4 + "\""); System.out.println("所有可能的IP地址:"); for (String ip : result4) { System.out.println(" " + ip); } System.out.println("期望: 所有可能的IP组合"); System.out.println(); // 测试用例5：数字长度小于4位 String s5 = "123"; List<String> result5 = solution.restoreIpAddresses(s5); System.out.println("测试用例5 - 输入: \"" + s5 + "\""); System.out.println("所有可能的IP地址:"); for (String ip : result5) { System.out.println(" " + ip); } System.out.println("期望: []"); System.out.println(); // 测试用例6：数字长度大于12位 String s6 = "123456789012345"; List<String> result6 = solution.restoreIpAddresses(s6); System.out.println("测试用例6 - 输入: \"" + s6 + "\""); System.out.println("所有可能的IP地址数量: " + result6.size()); System.out.println("期望: 0"); System.out.println(); // 测试用例7：全部为0 String s7 = "000000000000"; List<String> result7 = solution.restoreIpAddresses(s7); System.out.println("测试用例7 - 输入: \"" + s7 + "\""); System.out.println("所有可能的IP地址:"); for (String ip : result7) { System.out.println(" " + ip); } System.out.println("期望: [\"0.0.0.0\"] 只有一个有效IP"); System.out.println(); // 测试用例8：包含大于255的段 String s8 = "25625511135"; List<String> result8 = solution.restoreIpAddresses(s8); System.out.println("测试用例8 - 输入: \"" + s8 + "\""); System.out.println("所有可能的IP地址:"); for (String ip : result8) { System.out.println(" " + ip); } System.out.println("期望: []"); System.out.println(); // 测试用例9：最短有效IP String s9 = "1111"; List<String> result9 = solution.restoreIpAddresses(s9); System.out.println("测试用例9 - 输入: \"" + s9 + "\""); System.out.println("所有可能的IP地址:"); for (String ip : result9) { System.out.println(" " + ip); } System.out.println("期望: [\"1.1.1.1\"]"); System.out.println(); // 测试用例10：复杂情况 String s10 = "101023"; List<String> result10 = solution.restoreIpAddresses(s10); System.out.println("测试用例10 - 输入: \"" + s10 + "\""); System.out.println("所有可能的IP地址:"); for (String ip : result10) { System.out.println(" " + ip); } System.out.println("期望: [\"1.0.10.23\", \"1.0.102.3\", \"10.1.0.23\", \"10.10.2.3\", \"101.0.2.3\"]"); System.out.println(); // 测试用例11：包含连续0 String s11 = "100001"; List<String> result11 = solution.restoreIpAddresses(s11); System.out.println("测试用例11 - 输入: \"" + s11 + "\""); System.out.println("所有可能的IP地址:"); for (String ip : result11) { System.out.println(" " + ip); } System.out.println("期望: [\"100.0.0.1\", \"10.0.0.1\", \"1.0.0.1\"]"); System.out.println(); // 测试用例12：最大数字 String s12 = "255255255255"; List<String> result12 = solution.restoreIpAddresses(s12); System.out.println("测试用例12 - 输入: \"" + s12 + "\""); System.out.println("所有可能的IP地址:"); for (String ip : result12) { System.out.println(" " + ip); } System.out.println("期望: [\"255.255.255.255\"]"); System.out.println(); // 测试用例13：以0开头但有效 String s13 = "012345"; List<String> result13 = solution.restoreIpAddresses(s13); System.out.println("测试用例13 - 输入: \"" + s13 + "\""); System.out.println("所有可能的IP地址:"); for (String ip : result13) { System.out.println(" " + ip); } System.out.println("期望: 包含0开头的有效组合"); System.out.println(); // 测试用例14：多个0的情况 String s14 = "0000"; List<String> result14 = solution.restoreIpAddresses(s14); System.out.println("测试用例14 - 输入: \"" + s14 + "\""); System.out.println("所有可能的IP地址:"); for (String ip : result14) { System.out.println(" " + ip); } System.out.println("期望: [\"0.0.0.0\"]"); System.out.println(); // 测试用例15：所有可能的IP数量 String s15 = "111111111111"; List<String> result15 = solution.restoreIpAddresses(s15); System.out.println("测试用例15 - 输入: \"" + s15 + "\""); System.out.println("所有可能的IP地址数量: " + result15.size()); System.out.println("期望: 81种可能的IP组合"); System.out.println("前5个:"); for (int i = 0; i < Math.min(5, result15.size()); i++) { System.out.println(" " + result15.get(i)); } System.out.println(); } }