题目
有效 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 中的任何数字。你可以按 任何 顺序返回答案。
输入： s = "25525511135" 输出： ["255.255.11.135","255.255.111.35"] 复制代码
输入： s = "0000" 输出： ["0.0.0.0"] 复制代码
题解
package com.six.finger.leetcode.five; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Deque; import java.util.List; public class eighteen { public static void main(String[] args) { } public List<String> restoreIpAddresses(String s) { //临界条件的判断 int len = s.length(); //定义一个结果 List<String> res = new ArrayList<>(); // 如果长度不够，不搜索 if (len < 4 || len > 12) { return res; } // 设置存储path的子集 Deque<String> path = new ArrayDeque<>(4); int splitTimes = 0; //就是进行我们backtracing backtracing(s, len, splitTimes, 0, path, res); //返回结果 return res; } private void backtracing(String s, int len, int split, int begin, Deque<String> path, List<String> res) { //判断退出条件 if (begin == len) { if (split == 4) { res.add(String.join(".", path)); } return; } for (int i = 0; i < 3; i++) { if (begin + i >= len) { break; } int ipSegment = judgeIfIpSegment(s, begin, begin + i); if (ipSegment != -1) { // 在判断是 ip 段的情况下，才去做截取 path.addLast(ipSegment + ""); backtracing(s, len, split + 1, begin + i + 1, path, res); path.removeLast(); } } } //其实这个就是把string变成int类型 private int judgeIfIpSegment(String s, int left, int right) { int len = right - left + 1; // 大于 1 位的时候，不能以 0 开头 if (len > 1 && s.charAt(left) == '0') { return -1; } // 转成 int 类型 int res = 0; for (int i = left; i <= right; i++) { res = res * 10 + s.charAt(i) - '0'; } if (res > 255) { return -1; } return res; } } 复制代码
分析
这题还是蛮难的，因为他考察的知识点有点多，首先你要对ip的相关知识熟悉，然后你要对回溯熟悉，对怎么把一个string的字符变成int类型，等等，我也是看答案做的，哎，太菜了。不过还是和大家一起总结总结
- 第一步，就是做临界条件的判断，设置res，path，然后就是写回溯方法
- 写回溯方法的时候，设计回溯的参数这里一个有2个参数需要注意，一个说切割的参数，一个是我们加的点号的参数
- 然后就是写我们的结束条件了
- 之前就是我们的循环，3位为一个循环，也就是 0，1，2
- 然后判断每3位是不是一个ip端，通过ip变成数字之后 大小是0到255来判断
- 之后就是把对的加入到path中，然后继续backtraceing
- 最后回溯的时候remove调这个东西
结束
哈哈，越来越难了，大家加油，这种东西估计要多做几遍才行，我是一遍不能解决的，哎，太菜了
