算法-回溯篇07-复原 IP 地址

复原 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 中的任何数字。你可以按 任何 顺序返回答案。

解题思路

对字符串进行切割，然后判断割出来的每一段是否是合法的字符。

isLegal函数用于判断字符串是否在0-255这个范围；
backTrack函数用于回溯切割字符串；
其中这里不能是一个个字符去尝试切割，这样子时间复杂度太高了，我们需要对每次切割做出一个范围限定；
因为每一段的字符长度必须是1-3，那么我们就需要给后面的所有字符预留下合法的长度区间；
比如字符串的长度为4，那么肯定是四段长度为一，我们在遍历的时候，第一段还去尝试长度为2和3就没有意义了。

// 这里是左右区间
// 如果后面长度全是3，这里的左边界应该是l
// 如果后面长度全是1，这里的有边界应该是r
// 然后这一段长度肯定是1-3
//把限定条件一加上，可以减少很多不想必要的回溯
int l = s.size() - 3 * (3 - index), r = s.size() - (3 - index);
l = l > 0 ? l : 1;

然后每次切割完，把字符串传入函数判断合法，其他的地方都是回溯的模板了。

题解

class Solution {
public:
    vector ans;

    string path;

    bool isLegal(string s){
        if(s.size()  3){
            return false;
        }
        if(s.size() != 1 && s[0] == '0'){
            return false;
        }
        if(s.size() == 3){
            if(s = '0' && c  3 || s.size()  0 ? l : 1;
        for(int i = l; i  restoreIpAddresses(string s) {
        BackTrack(s, 0);
        return ans;
    }
};

总结

这道题目最重要的地方就是不能暴力去切割字符串，应该对整体的长度做出假设性极限，然后在极限的范围内切割。

文章来源于互联网:算法-回溯篇07-复原 IP 地址

相关推荐: “文心一言”的使用

介绍 官方定义它是有用、有趣、有温度的智能伙伴。和ChatGPT一样，它既能写文案、读文档，又能脑洞大开、答疑解惑。还能倾听你的故事、感受你的心声。 它既是ai人工智能，又是工作助理，能够自动处理生活和工作中的各种问题，是问题的解决者。 可以把它看成一个“人”…