题目:
题解:
思路:
我们要知道IP的格式,每位是在0~255之间,
注意: 不能出现以0开头的两位以上数字,比如012,08...
思路一:暴力法
我们把所有出现可能都列举出来,看是否满足条件.
思路二:回溯算法
代码:
1. 代码一:(思路一)
/** * code93 */
import java.util.*;
public class code93 {
public static List<String> restoreIpAddresses(String s) {
List<String> res = new ArrayList<>();
int n = s.length();
for (int i = 0; i < 3; i++) {
for (int j = i + 1; j < i + 4; j++) {
for (int k = j + 1; k < j + 4; k++) {
if (i < n && j < n && k < n) {
String tmp1 = s.substring(0, i + 1);
String tmp2 = s.substring(i + 1, j + 1);
String tmp3 = s.substring(j + 1, k + 1);
String tmp4 = s.substring(k + 1);
if (helper(tmp1) && helper(tmp2) && helper(tmp3) && helper(tmp4)) {
res.add(tmp1 + "." + tmp2 + "." + tmp3 + "." + tmp4);
}
}
}
}
}
return res;
}
public static boolean helper(String tmp) {
if (tmp == null || tmp.length() == 0 || tmp.length() > 3 || (tmp.charAt(0) == '0' && tmp.length() > 1)
|| Integer.parseInt(tmp) > 255) {
return false;
}
return true;
}
public static void main(String[] args) {
String str = "25525511135";
List<String> list = restoreIpAddresses(str);
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
}
}
2. 代码二:(思路二)
/** * code93 */
import java.util.*;
public class code93 {
// 解法二:
public static List<String> restoreIpAddresses(String s) {
List<String> res = new ArrayList<>();
int n = s.length();
backtrack(0, "", 4, s, res, n);// flag == 4, 表示 IP地址分为 4 段
return res;
}
public static void backtrack(int i, String tmp, int flag, String s, List<String> res, int n) {
if (i == n && flag == 0) {
res.add(tmp.substring(0, tmp.length() - 1));// 最后加了个"." 要去掉
return;
}
if (flag < 0) {
return;
}
for (int j = i; j < i + 3; j++) {
if (j < n) {
if (i == j && s.charAt(j) == '0') {
backtrack(j + 1, tmp + s.charAt(j) + ".", flag - 1, s, res, n);
break;
}
if (Integer.parseInt(s.substring(i, j + 1)) <= 255) {
backtrack(j + 1, tmp + s.substring(i, j + 1) + ".", flag - 1, s, res, n);
}
}
}
}
public static void main(String[] args) {
String str = "25525511135";
List<String> list = restoreIpAddresses(str);
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
}
}