题意整理

  • 有一个只包含数字的字符串，将该字符串转化成IP地址的形式，返回所有可能的情况。
  • Ip地址由四段组成，每段用"."隔开，每一段对应的数值范围在0-255之间。

方法一（四层循环）

1.解题思路

利用四层循环访问所有可能的情况，当每一段长度之和等于字符串总长度时，排除掉不合法的情况（比如某一段的值大于255，或者拼接后的ip长度不等于字符串总长度加3）。将可能的加过加入到res，每次加入之后都要重置ip为空。

动图展示： alt

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return string字符串ArrayList
     */
    public ArrayList<String> restoreIpAddresses (String s) {
        //用于记录所有合法字符串
        ArrayList<String> res=new ArrayList<>();
        //记录拼接出的ip地址
        StringBuilder ip=new StringBuilder();
        //四层循环
        for(int i=1;i<=3;i++){
            for(int j=1;j<=3;j++){
                for(int k=1;k<=3;k++){
                    for(int l=1;l<=3;l++){
                        //必须每一段的长度之和等于字符串总长度
                        if(i+j+k+l==s.length()){
                            //每一段对应的值
                            int a=Integer.parseInt(s.substring(0,i));
                            int b=Integer.parseInt(s.substring(i,i+j));
                            int c=Integer.parseInt(s.substring(i+j,i+j+k));
                            int d=Integer.parseInt(s.substring(i+j+k));
                            //只要大于255，则不合法
                            if(a>255||b>255||c>255||d>255){
                                continue;
                            }
                            //拼接成ip地址
                            ip.append(a).append(".")
                              .append(b).append(".")
                              .append(c).append(".")
                              .append(d);
                            //如果长度刚好等于原字符串长度加3，则合法
                            if(ip.length()==s.length()+3){
                                res.add(ip.toString());
                            }
                            //清空ip
                            ip=new StringBuilder();
                        }
                    }
                }
            }
        }
        return res;
    }
}

3.复杂度分析

  • 时间复杂度：需要4层循环，每层循环最多执行3次，均为常数级别，所以时间复杂度为O(1)O(1)。
  • 空间复杂度：需要额外常数级别的空间，所以空间复杂度是O(1)O(1)。

方法二（回溯）

1.解题思路

  • 递归终止条件：走完整个字符串。
  • 递归如何推进：首先在每一层中排除掉不合法的情况，将可能的每一段加入到ip，同时记录每个变量的变化。如果不合法，要回溯到加入某一段之前ip对应的状态。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return string字符串ArrayList
     */
    //用于记录所有合法字符串
    ArrayList<String> res=new ArrayList<>();
    String s;
    
    public ArrayList<String> restoreIpAddresses (String s) {
        this.s=s;
        //进行深度优先搜索
        dfs(0,0,new StringBuilder());
        return res;
    }
    
    private void dfs(int index,int depth,StringBuilder ip){
        //记录ip长度
        int len=ip.length();
        if(index==s.length()){
            //如果字符串走完，并且刚好分为四段，则加入到res
            if(depth==4){
                //需要删掉多加的一个"."
                ip.deleteCharAt(ip.length()-1);
                res.add(ip.toString());
            }
            return;
        }
        for(int i=1;i<=3;i++){
            //如果超过字符串长度，直接终止
            if(i+index>s.length()) break;
            //截取的子串对应的数值
            int num=Integer.parseInt(s.substring(index,index+i));
            //不合法的情况
            if(num>255||String.valueOf(num).length()!=i){
                continue;
            } 
            //添加到ip
            ip.append(num).append(".");
            dfs(index+i,depth+1,ip);
            //回溯到未添加前的情况
            ip.setLength(len);
        }
    }
}

3.复杂度分析

  • 时间复杂度：假设k=4是ip地址的段数，由于ip地址的每一段的位数不会超过3，所以在递归的每一层，我们最多深入到下一层的三种情况，所以时间复杂度为O(3k)O(3^k)。
  • 空间复杂度：递归使用的空间与递归的最大深度k成正比，需要额外大小为k的空间，所以空间复杂度是O(k)O(k) 。