LeetCode刷题【93】复原IP地址

给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。

有效 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 地址。

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

输入：s = "1111"
输出：["1.1.1.1"]

示例 4：

输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]

示例 5：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示：

• 0 <= s.length <= 3000
• s 仅由数字组成

题解

回溯。具体思路就是，每次尝试截取1-3位字符，判断是否符合0-255之间的数值，这里单独写个方法判断截取出来的字符串是否符合ip中的数字的要求。不能是0开头的字符，但是可以是单独的一个字符“0”。

另外，终止条件必须是凑齐了4个数字，且最后截取到了提供的字符串的最后一位

if (strArr.size()==3 && lastIndex < s.length()){
                continue;
            }

这样的逻辑是，已经存了3个数字，且最后截取到了提供的字符的最后一位才会继续执行。这部分甚至可以继续深入优化下，比如已经存了2个数字，且剩余字符位数小于7位，因为每个数字可能为1-3位数。或者，已经存了1个数字，且剩余字符位数小于10位这样的逻辑。

import java.util.ArrayList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    private List<String> res = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        List<String> strArr = new ArrayList<>();
        dfs(strArr,s,0);

        return res;
    }


    private void dfs(List<String> strArr, String s, int startIndex){
        for (int i = 1; i <= 3; i++) {
            //尝试往后截取1-3位
            int lastIndex = startIndex+i;
            //如果当前递归收集到的数组中已经有三个，并且，后面要截取的字符没能截取到给定字符串的最后一位
            //结束当前长度的尝试，进入下一个更长长度的截取尝试
            if (strArr.size()==3 && lastIndex < s.length()){
                continue;
            }
            if (lastIndex > s.length()){
                //substring最后一次截取如果index超出了长度，会产生重复，且这个分支说明已经结束了
                return;
            }

            String str = s.substring(startIndex,lastIndex);
            if (validateIpNum(str, strArr.size())){
                strArr.add(str);
                if (strArr.size()==4 && lastIndex == s.length()){
                    String newStr = String.join(".",strArr);
                    System.out.println(newStr);
                    res.add(newStr);

                }
                dfs(strArr,s,lastIndex);
                strArr.remove(strArr.size()-1);
            }

        }
    }

    private boolean validateIpNum(String numStr,int numIndex){
        if (numStr.length()>1 && numStr.startsWith("0")){
            return false;
        }
        int num = Integer.parseInt(numStr);
        return num < 256;
    }
}
//leetcode submit region end(Prohibit modification and deletion)