题目

现在有一个只包含数字的字符串，将该字符串转化成IP地址的形式，返回所有可能的情况。

例如：

给出的字符串为"25525522135",

返回["255.255.22.135", "255.255.221.35"]. (顺序没有关系)

数据范围：

字符串长度 0≤n≤12

要求：

空间复杂度 O(n!),时间复杂度 O(n!)

注意：

ip地址是由四段数字组成的数字序列，格式如 "x.x.x.x"，其中 x 的范围应当是 [0,255]。

示例1

输入：

"25525522135"

返回值：

["255.255.22.135","255.255.221.35"]

示例2

输入：

"1111"

返回值：

["1.1.1.1"]

示例3

输入：

"000256"

返回值：

[]

---

思路1：枚举

对于IP字符串，如果只有数字，则相当于需要将IP地址的三个点插入字符串中，而第一个点的位置只能在第一个字符、第二个字符、第三个字符之后，而第二个点只能在第一个点后1-3个位置之内，第三个点只能在第二个点后1-3个位置之内，且要要求第三个点后的数字数量不能超过3，因为IP地址每位最多3位数字。

具体做法：

• step 1：依次枚举这三个点的位置。
• step 2：然后截取出四段数字。
• step 3：比较截取出来的数字，不能大于255，且除了0以外不能有前导0，然后才能组装成IP地址加入答案中。

---

代码1

import java.util.*;public class Solution {public ArrayList<String> restoreIpAddresses (String s) {ArrayList<String> res = new ArrayList<String>();int n = s.length();//遍历IP的点可能的位置（第一个点）for (int i = 1; i < 4 && i < n - 2; i++) {//第二个点的位置for (int j = i + 1; j < i + 4 && j < n - 1; j++) {//第三个点的位置for (int k = j + 1; k < j + 4 && k < n; k++) {//最后一段剩余数字不能超过3if (n - k >= 4) {continue;}//从点的位置分段截取String a = s.substring(0, i);String b = s.substring(i, j);String c = s.substring(j, k);String d = s.substring(k);//IP每个数字不大于255if (Integer.parseInt(a) > 255 || Integer.parseInt(b) > 255 ||Integer.parseInt(c) > 255 || Integer.parseInt(d) > 255) {continue;}//排除前导0的情况if ((a.length() != 1 && a.charAt(0) == '0') || (b.length() != 1 &&b.charAt(0) == '0') ||  (c.length() != 1 && c.charAt(0) == '0') ||(d.length() != 1 && d.charAt(0) == '0')) {continue;}//组装IP地址String temp = a + "." + b + "." + c + "." + d;res.add(temp);}}}return res;}
}

---

思路2：递归+回溯

对于IP地址每次取出一个数字和一个点后，对于剩余的部分可以看成是一个子问题，因此可以使用递归和回溯将点插入数字中。

具体做法：

• step 1：使用step记录分割出的数字个数，index记录递归的下标，结束递归是指step已经为4，且下标到达字符串末尾。
• step 2：在主体递归中，每次加入一个字符当数字，最多可以加入三个数字，剩余字符串进入递归构造下一个数字。
• step 3：然后要检查每次的数字是否合法（不超过255且没有前导0）
• step 4：合法IP需要将其连接，同时递归完这一轮后需要回溯。

---

代码2

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** @param s string字符串* @return string字符串ArrayList*/public ArrayList<String> restoreIpAddresses (String s) {// 对于IP地址每次取出一个数字和一个点后，对于剩余的部分可以看成是一个子问题，因此可以使用递归和回溯将点插入数字中。ArrayList<String> res = new ArrayList<>();dfs(s, res, 0, 0);return res;}//记录IP被分段形成的数字字符串private String nums = "";public void dfs(String s, ArrayList<String> res, int step, int index) { //step表示第几个数字,index表示字符串下标//当前分割出的字符串String cur = "";//分割出了4个数字if (step == 4) {//下标必须走到尾部if (index != s.length()) {return;} else {res.add(nums);}} else {//最长遍历3位for (int i = index; i < index + 3 && i < s.length(); i++) {cur += s.charAt(i);//转数字进行比较int num = Integer.parseInt(cur);String temp = nums;//不能超过255且不能有前导0if (num <= 255 && (cur.length() == 1 || cur.charAt(0) != '0')) {//添加点if (step - 3 != 0) {nums += cur + ".";} else {nums += cur;}//递归查找下一个数字dfs(s, res, step + 1, i + 1);//回溯nums = temp;}}}}
}