93.复原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 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例1：

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

示例2:

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

示例3:

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

提示：

• 1 <= s.length <= 20
• s 仅由数字组成

思路与算法

1、首先，定义一个递归函数 restoreIpAddresses，该函数接收以下参数：原始字符串 s、当前正在构建的IP地址 current、已经构建的IP地址部分数量 count、结果集 result。

2、在 restoreIpAddresses 函数中，首先检查是否已经构建了4个IP地址部分，如果是，则判断是否已经遍历完整个字符串 s，如果是，则将 current 加入到结果集 result 中。

3、如果还没有构建完4个IP地址部分，则进行以下操作：

• 使用一个循环遍历，从当前位置开始，尝试截取长度为1、2或3的子串作为一个IP地址部分。
• 对于每个尝试的子串，需要满足以下条件才能继续递归构建IP地址：
  • 子串的长度大于0且小于等于3。
  • 如果子串长度大于1，那么子串不能以0开头。
  • 子串表示的数值必须在0到255之间。
• 如果满足条件，则将该子串加入到当前正在构建的IP地址 current 中，并递归调用 restoreIpAddresses，同时更新 count 值加1。
• 在递归调用返回后，需要将当前尝试的子串从 current 中移除，以便尝试下一个可能的子串。

4、最后，返回结果集 result。

通过以上步骤，递归函数将会生成所有可能的合法IP地址组合，并将其存储在结果集中返回。

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
      	//初始时，已经收集到的段数为0，当前索引为0，子结果为空字符串。
        dfs(0, 0, "", s, result);
        return result;
    }
		
  //dfs接收已经收集到的段数 collectedCount，当前索引 curldx，当前子结果 subResult，输入字符串 s 和结果列表 result
    public void dfs(int collectedCount, int curldx, String subResult, String s, List<String> result){
        //满足条件
        if(collectedCount == 4 && curldx == s.length()){//收集到了4个段并且当前索引已经遍历完整个字符串
            result.add(subResult);
            return;
        }

        //尝试不同长度的子串
        for(int i = 1; i <= 3; i++){//从1到3遍历，尝试截取长度为1、2或3的子串。
          
          //在截取子串之前，先检查是否超出了字符串的长度。如果超出了，结束循环，因为无法继续截取合法的子串。
            if(curldx + i > s.length()) {
              break; //不符合条件
            }

            String curString = s.substring(curldx, curldx+i); //截取子串
          
          //两个条件的判断: 1、子串的长度大于1且第一个字符为0 2、串转换为整数后大于等于256
          //子串的长度大于1只是为了排除掉以0开头的多位数子串，因为以0开头的子串在表示IP地址时是不合法的。
            if((curString.length() > 1 && curString.charAt(0) == '0') || Integer.parseInt(curString)>= 256){
                //不符合条件
                break;
            }
          
          //当前索引更新为当前索引加上子串长度
          //子结果更新为当前子结果加上子串（如果是第一个段，则直接加上子串，否则加上点和子串）
            dfs(collectedCount+1, curldx + i,collectedCount==0 ? subResult+curString :subResult+"."+curString, s, result);
        }
    }
}

复杂度分析

• 时间复杂度：$O(4^n)$
• 空间复杂度：$O(4^n)$