后端开发刷题 | 数字字符串转化成IP地址

描述

现在有一个只包含数字的字符串，将该字符串转化成IP地址的形式，返回所有可能的情况。

例如：

给出的字符串为"25525522135",

返回["255.255.22.135", "255.255.221.35"]. (顺序没有关系)

数据范围：字符串长度 0≤n≤12

要求：空间复杂度 O(n!)，时间复杂度 O(n!)

注意：ip地址是由四段数字组成的数字序列，格式如 "x.x.x.x"，其中 x 的范围应当是 [0,255]。

示例1

输入：

"25525522135"

返回值：

["255.255.22.135","255.255.221.35"]

示例2

输入：

"1111"

返回值：

["1.1.1.1"]

示例3

输入：

"000256"

返回值：

[]

思路分析：

该题可以使用递归+回溯法解决，

对于IP地址每次取出一个数字和一个点后，对于剩余的部分可以看成是一个子问题，因此可以使用递归和回溯将点插入数字中。

具体做法：

• step 1：使用step记录分割出的数字个数，index记录递归的下标，结束递归是指step已经为4，且下标到达字符串末尾。
• step 2：在主体递归中，每次加入一个字符当数字，最多可以加入三个数字，剩余字符串进入递归构造下一个数字。
• step 3：然后要检查每次的数字是否合法（不超过255且没有前导0）.
• step 4：合法IP需要将其连接，同时递归完这一轮后需要回溯。

图示：

逻辑：

• 基本情况：如果 step 等于 4（即已经构建了四个部分），则检查是否已经遍历了整个字符串 s（index == s.length()）。如果是，则将当前构建的 IP 地址（存储在 nums 中）添加到结果列表 res 中。
• 递归情况：
  • 从 index 开始，尝试构建长度为 1、2 或 3 的字符串（表示 IP 地址的一个部分），同时确保不会超出 s 的长度。
  • 对于每个可能的长度，检查构建的字符串（即 IP 地址的一个部分）是否满足条件（值在 0 到 255 之间，且不以 0 开头除非它本身是 0）。
  • 如果满足条件，则将其添加到 nums 中（可能需要添加一个点分隔符，除非它是最后一个部分），然后递归地调用 dfs 方法，step 增加 1，index 跳到当前字符串的下一个字符。
  • 在递归调用之后，需要回溯，即将 nums 恢复到递归调用之前的状态，以便尝试其他可能的构建方式。

代码：

import java.util.*;


public class Solution {

    public String nums="";
    public void dfs(String s,ArrayList<String> res,int step,int index){
        String cur="";
        if(step==4){
            if(index!=s.length()){
                return;
            }
            res.add(nums.toString());
        }else{
            for(int i=index;i<index+3&&i<s.length();i++){
                cur+=s.charAt(i);
                int num=Integer.parseInt(cur);
                String temp=nums;
                if(num<=255&&(cur.length()==1||cur.charAt(0)!='0')){
                    if(step-3!=0){
                        nums+=cur+".";
                    }else{
                        nums+=cur;
                    }
                    dfs(s,res,step+1,i+1);
                    nums=temp;

                }
            }
        }
    }
    /**
     * 
     * @param s string字符串 
     * @return string字符串ArrayList
     */
    public ArrayList<String> restoreIpAddresses (String s) {
        ArrayList<String> list=new ArrayList<>();
        dfs(s,list,0,0);
        return list;
        
    }
}