7.7复原IP地址(LC93-M)

2023-12-29 16:37:58

算法:

根据题意

有效的 IP 地址 :

(1)由四个整数构成

(2)每个整数位于 0 到 255 之间

(3)每个整数不能含有前导 0,如011、021等,但是可以有单独的一个“0”

(4)整数之间用 '.' 分隔。

其实本质上就是分割问题,把一串数字分成四部分,每部分要满足条件(2)和(3),这四个部分用字符'.'串起来,所以还是用回溯

画树:

回溯三部曲:

1.确定函数返回值和参数

返回值:void

参数:

String s(题目自带)

int startindex:记录下一层递归分割的起始位置。

Int?pointNum;记录添加“.”的数量(要加3个)

2. 确认终止条件,收集合法的数字段:

本题明确要求只会分成4段,所以不能用切割线切到最后作为终止条件,而是分割的段数作为终止条件。

pointNum表示逗点数量,pointNum为3说明字符串分成了4段了。

3.单层递归逻辑:

for循环:

//收集结果

for (int i = startIndex; i < s.length(); i++)

[startIndex, i] 这个区间就是截取的子串,需要判断这个子串是否合法。

如果合法就在字符串后面加上符号.表示已经分割。

如果不合法就结束本层循环

//递归

同时记录分割符的数量pointNum 要 +1

backtracking(s, i+2, pointNum)

i+2,可以看下图:

i=3时,下一层递归的startindex=5


//回溯

pointNum要-1

将刚刚加入的分隔符.?删掉

判断子串是否合法

主要考虑到如下三点:

  • 段位以0为开头的数字不合法
  • 段位里有非正整数字符不合法
  • 段位如果大于255了不合法

判断时遵循“左闭右闭”

先判错

注意:

1.这里的全局变量没有path了

因为result就是一个一维数组,数组由字符串构成

什么时候需要path?

result为二维数组时,比如

正确代码:

class Solution {
    //全局变量result
    List<String> result = new LinkedList<>();
    
    public List<String> restoreIpAddresses(String s) {
        if (s.length()>12) return result;
        baktracking (s, 0, 0);
        return result;

    }
    void baktracking (String s, int startindex, int pointNum){
    //确定终止条件,收集结果
    if (pointNum == 3) {
    //判断第三个"."之后的第四段字段是否合法(前三段在单层递归逻辑中判断是否合法)
    //若合法,则将该合法字符s加入reslt
    //索引从0开始
    if (isvalid (s, startindex, s.length()-1)){
        result.add(s);
    }
    return;}
    //单层递归逻辑
    for (int i= startindex; i< s.length(); i++){
        //判断是否合法,合法就加"."
        if (isvalid (s, startindex, i)) {
        //因为string不可变,所以要重新赋值给一个新的string
        s = s.substring(0, i+1)+"."+s.substring(i+1);
        //substring左闭右开,所以两个都是i+1
        pointNum++;
        //递归
        baktracking (s, i+2, pointNum);
        //回溯
        pointNum--;
        //因为string不可变,所以要重新赋值给一个新的string
        s = s.substring(0, i+1)+s.substring(i+2);
        //第二个substring从i+2开始,因为前面有个“.”      
        }
        else break;
    }

    }

   
    //判断字符串是否合法,左闭右闭
    //先判错
    //1.每位是正整数,在0-9(题目说s 仅由数字组成)
    //2.每个整数位于 0 到 255 之间
    //3.不能含有前导 0
    boolean isvalid (String s, int start, int end) {
        //if (s.length()>12) return false;这里不能写这句话,因为S里面可能有“.”,确实不止12
        if (start > end) return false;
        int num = 0;
        for (int i= start; i<=end ;i++){
            if (s.charAt(i) < '0' || s.charAt(i) > '9') return false;
            num = num*10+ (s.charAt(i)-'0');
            if (num > 255) return false;
        }
        if (s.charAt(start) == '0' && start != end) return false;
        return true;
    }
}

优化:

由于string不能直接改,每次都要赋值个新的s,比较占空间;可以使用stringBuilder

优化后的正确代码:

class Solution {
    List<String> result = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        StringBuilder sb = new StringBuilder(s);
        backTracking(sb, 0, 0);
        return result;
    }
    private void backTracking(StringBuilder s, int startIndex, int dotCount){
        if(dotCount == 3){
            if(isValid(s, startIndex, s.length() - 1)){
                result.add(s.toString());
            }
            return;
        }
        for(int i = startIndex; i < s.length(); i++){
            if(isValid(s, startIndex, i)){
                s.insert(i + 1, '.');
                backTracking(s, i + 2, dotCount + 1);
                s.deleteCharAt(i + 1);
            }else{
                break;
            }
        }
    }
    //[start, end]
    private boolean isValid(StringBuilder s, int start, int end){
        if(start > end)
            return false;
        if(s.charAt(start) == '0' && start != end)
            return false;
        int num = 0;
        for(int i = start; i <= end; i++){
            int digit = s.charAt(i) - '0';
            num = num * 10 + digit;
            if(num > 255)
                return false;
        }
        return true;
    }
}

时间空间复杂度:

文章来源:https://blog.csdn.net/m0_50696252/article/details/135288918
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。