题解 | #数字字符串转化成IP地址#

想象一下递归树的结构，其中每个节点代表当前递归的状态。在这个特定的问题中，我们要解决的问题是将字符串 s 划分为四个IPv4地址段。

以下是如何可视化 restoreIpAddresses 方法的递归过程：

1. 根节点：代表初始状态，tmp 和 res 为空，cur 为 0，表示我们从字符串 s 的开始处进行划分。
2. 分支：每个节点根据当前索引 cur 可以生成1到3位的数字段（不能以0开头，除非数字段是0本身）。每个可能的数字段都是一个分支。
3. 深度优先搜索（DFS）：从根节点开始，我们沿着每个分支向下搜索，直到无法继续生成有效的数字段或达到字符串的末尾。
4. 剪枝：在搜索过程中，我们使用剪枝条件来减少不必要的搜索：如果当前未处理的字符串长度 s.length() - cur 大于剩余段数乘以3，提前返回（因为不可能生成足够的段）。如果小于剩余段数，也提前返回（因为当前剩余的字符串长度不足以生成所需的段数）。
5. 回溯：在每个分支的末尾，我们使用 tmp.remove(tmp.size() - 1) 进行回溯。这表示我们撤销了上一步的决策，回到前一个状态，然后尝试下一个可能的数字段。
6. 构建结果：当我们成功地生成了四个段，并且所有的字符都被使用时（tmp.size() == 4 && cur == s.length()），我们将这些段组合成一个IPv4地址，并将其添加到结果列表 res 中。
7. 终止条件：如果 tmp 中的段数已经达到4，并且当前索引 cur 等于字符串 s 的长度，我们找到了一个有效的IPv4地址组合。
8. 前导0的处理：如果生成的数字段 num 为0，并且当前索引 i 不等于起始索引 cur（即存在前导0），则使用 break 退出当前循环，避免将无效的段加入到 tmp 中。

可视化这个过程，可以想象一个树状图，其中每个节点代表一个递归调用的状态，每个节点的子节点代表从该状态生成的所有可能的数字段。树的深度为字符串 s 的长度，宽度为可能的数字段的组合数量。

通过这种方式，我们可以清晰地看到递归过程中的所有可能路径，以及如何通过回溯来探索不同的组合。这也展示了为什么不需要清空 tmp：因为我们希望保留之前的决策，以便在回溯时可以重新使用它们。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串ArrayList
     */
     ArrayList<String> res=new ArrayList<>();
    ArrayList<String> tmp=new ArrayList<>();
     
    public ArrayList<String> restoreIpAddresses (String s) {
        // write code here
        // 限制每一个[1,3]位置以及如果是3，那么数字小于255，否则，挪给别的，
        // >1则不能以0开头
        // 根据位数判断
        dfs(s,0);
        return res;

      }
      public void dfs(String s,int cur)
      {
        if(tmp.size()==4&& cur==s.length())
        {
            res.add(tmp.get(0)+"."+tmp.get(1)+"."+tmp.get(2)+"."+tmp.get(3));
        }
        if(s.length()-cur>3*(4-tmp.size()))//每段大于3
        {
            return;
        }
        if(s.length()-cur<4-tmp.size())//小于1
        {
            return;
        }
        int num=0;
        for(int i=cur;i<cur+3&&i<s.length();i++)//一个一个数字的判断
        {//0,1,2
            num=num*10+(s.charAt(i)-'0');//数字
            if(num<0||num>255)//数字越界了就不要了，

            {
                break;
            }
            tmp.add(s.substring(cur,i+1));//截取【0，255】之间的数字
            dfs(s,i+1);//继续判断
            tmp.remove(tmp.size()-1);//为啥？
            // 回溯允许算法“回到”上一个状态，重新考虑不同的数字组合。
            if(num==0)
            {
                break;//只能0.不能02|09这些
            }


        }
      }
}