代码随想录算法训练营之JAVA｜第二十四天| 93. 复原 IP 地址

今天是第24天刷leetcode，立个flag，打卡60天。

算法挑战链接

93. 复原 IP 地址https://leetcode.cn/problems/restore-ip-addresses/

第一想法

题目理解：将一串数字字符串变成正确的ip格式的字符串。

这类题目是切分字符串，ip一共有四组，所以是切分三次。

切分字符串的方法第一想到的就是回溯算法。那么使用回溯算法我们也可以和递归那样分三步走

第一步：确定入参和返回值

void backtracking3(String s, List<String> result);
回溯算法的返回值一般都是void
入参不确定可以先做后面的，使用的时候发现没有就可以确定为入参了

第二步：确定终止条件

        if (array.length == 4) {//判断是否是一个正缺的ipif (isIp(array[3])) {result.add(s);}return;}很明显的终止条件，字符串被切割成四份，且每一份都在0-255范围内

第三步：在当前的操作

        String tmp = array[array.length - 1];for (int i = 0; i < tmp.length() - 1; i++) {String lastString = tmp.substring(i + 1);String preString = tmp.substring(0, i + 1);String newString = combineString(array, preString, lastString);backtracking3(newString, result);}
找到最后一份，不断的切分，比如111， 会根据1.11、11.1 这样来切分

在回溯算法中是可以考虑剪枝的。

        for (int i = 0; i < array.length - 1; i++) {if (! isIp(array[i])) return;}
如果前面的数字不符合ip的规范，那么后面就没有必要在进行递归了

 因此完成的代码如下：

class Solution {public List<String> restoreIpAddresses(String s) {List<String> result = new ArrayList<>();if (s.length() > 12) return result;backtracking3(s, result);return result;}void backtracking3(String s, List<String> result) {String[] array = s.split("\\.");for (int i = 0; i < array.length - 1; i++) {if (! isIp(array[i])) return;}if (array.length == 4) {//判断是否是一个正缺的ipif (isIp(array[3])) {result.add(s);}return;}String tmp = array[array.length - 1];for (int i = 0; i < tmp.length() - 1; i++) {String lastString = tmp.substring(i + 1);String preString = tmp.substring(0, i + 1);String newString = combineString(array, preString, lastString);backtracking3(newString, result);}}private static boolean isIp(String s) {if (s.startsWith("0") && s.length() > 1) return false;long currentNum = Long.parseLong(s);return currentNum >= 0 && currentNum <= 255;}private String combineString(String[] array, String preString, String lastString) {StringBuilder sb = new StringBuilder();for (int i = 0; i < array.length - 1; i++) {sb.append(array[i]).append(".");}sb.append(preString).append(".").append(lastString);return sb.toString();}
}

实现过程中遇到哪些困难 

实现过程中遇到的困难有

1. 错误判断 0开头的也算符合，如032
2. 错误判断 0不符合Ip规则，如 0.0.0.0
3. 在进行字符串转换数字的时候，没有考虑到较大的数，使用了Integer.parseInt方法，报错了。
4. 没有对字符串做过滤，导致 long.parseLong方法报错， 如999999999999999999

今日收获

       做题的时候应该需要看一下是否需要前置性做校验。