leetCode 93.复原 IP 地址 + 回溯算法 + 图解 + 笔记

93. 复原 IP 地址 – 力扣（LeetCode）

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

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

题目要求：给我们个字符串，切割成一个合法的IP地址（IPv4形式）

思路和分析(O_O)?  

• 切割问题可以使用回溯搜索法把所有可能性搜出来
• 切割问题可以抽象为树形结构
• 判断子串是否合法

（一）判断子串是否合法，主要考虑三点： 

• 1）以0为开头的数字不合法

if(s[start] == '0' && start != end) { // 0开头的数字不合法
    return false;
}

• 2）有非正整数字符不合法

if(s[i]>'9' || s[i]<'0') { // 遇到非数字字符不合法
    return false;
}

• 3）如果大于255了不合法

if(num > 255) return false;// 如果大于255了，不合法

// 判断字符串s在左闭右闭区间[start,end]所组成的数字是否合法
bool isValid(const string& s,int start,int end) {
    if(start > end) return false;
    if(s[start] == '0' && start != end) { // 0开头的数字不合法
        return false;
    }
    // num = num*10+(s[i]-'0');
    // "225" -> 2*10=20 
    //          20*10+2=22 
    //          22*10+5=225
    int num = 0;
    for(int i=start;i<=end;i++) { 
        if(s[i]>'9' || s[i]<'0') { // 遇到非数字字符不合法
            return false;
        }
        num = num*10+(s[i]-'0');
        if(num > 255) return false;// 如果大于255了，不合法
    }
    return true;
}

（二）回溯三部曲：

1.确定递归参数和返回类型

• startIndex:记录搜索的起始位置，是下一次递归分割的起始位置，可确保不会重复分割
• pointNum:记录添加逗点的数量

void backtracking(string& s,int startIndex,int pointNum)

2.确定递归终止条件

• leetCode 131.分割回文串是以切割线到最后作为终止条件
• 本题是 IPv4 地址，故所给字符串会被分成 4段，所以以分割的段数作为终止条件
• 如果最后一段，也就是第四段字符串合法，才加入结果集result中

if(pointNum == 3) { // 逗点数量为3时，分隔结束
    // 判断第四段字符串是否合法，如果合法就放进result中
    if(isValid(s,startIndex,s.size()-1)) {
        result.push_back(s);
    }
    return;
}

3.单层搜索的逻辑

[startIndex, i] 这个区间可用来截取的子串，接着判断这个子串是否合法

• 1）如果合法，则在其后加上符号‘.’ 来表示已经分割
• 2）如果不合法就直接结束本层循环，在图中表现为剪掉分支

递归和回溯的过程：

• 递归调用时，下一层递归的 startIndex 要从 i + 2 开始（在字符串中加入分隔符‘.’），还有pointNum++，表示分隔符的数量增加一个；
• 回溯时，将刚刚加入的分隔符 . 删掉就行，还有 pointNum—

for(int i=startIndex;i<s.size();i++) {
    if(isValid(s,startIndex,i)){     // 判断 [startIndex,i] 这个区间的子串是否合法
        s.insert(s.begin()+i+1,'.'); // 在i的后面插入一个逗点
        pointNum++;
        backtracking(s,i+2,pointNum);// 插入逗点之后下一个子串的起始位置为i+2
        pointNum--;                  // 回溯
        s.erase(s.begin()+i+1);      // 回溯删掉逗点
    }else break;                     //不合法，直接结束本层for循环
}

C++代码：

/*
    切割问题可以使用回溯搜索法把所有可能性搜出来
    切割问题可以抽象为树形结构
    判断子串是否合法，主要考虑三点：
        1).以0为开头的数字不合法
        2).有非正整数字符不合法
        3).如果大于255了不合法

    回溯三部曲：
        1.确定递归参数和返回类型
            startIndex:记录搜索的起始位置，是下一次递归分割的起始位置，可确保不会重复分割
            pointNum:记录添加逗点的数量
        2.确定递归终止条件
            - leetCode 131.分割回文串是以切割线到最后作为终止条件
            - 本题是IPv4地址，故所给字符串会被分成4段，所以以分割的段数作为终止条件
        3.单层搜索的逻辑
            [startIndex, i] 这个区间可用来截取的子串，接着判断这个子串是否合法
            1).如果合法，则在其后加上符号'.' 来表示已经分割
            2).如果不合法就直接结束本层循环，在图中表现为剪掉分支
            递归和回溯的过程：
                递归调用时，下一层递归的startIndex要从 i + 2开始（在字符串中加入分隔符.），还有pointNum++，表示分隔符的数量增加一个
                回溯时，将刚刚加入的分隔符 . 删掉就行，还有pointNum--


*/  
class Solution {
public:
    vector<string>result;// 记录结果
    // 判断字符串s在左闭右闭区间[start,end]所组成的数字是否合法
    bool isValid(const string& s,int start,int end) {
        if(start > end) return false;
        if(s[start] == '0' && start != end) { // 0开头的数字不合法
            return false;
        }
        int num = 0;
        for(int i=start;i<=end;i++) { 
            if(s[i]>'9' || s[i]<'0') { // 遇到非数字字符不合法
                return false;
            }
            num = num*10+(s[i]-'0');
            if(num > 255) return false;// 如果大于255了，不合法
        }
        return true;
    }
    void backtracking(string& s,int startIndex,int pointNum) {
        if(pointNum == 3) { // 逗点数量为3时，分隔结束
            // 判断第四段字符串是否合法，如果合法就放进result中
            if(isValid(s,startIndex,s.size()-1)) {
                result.push_back(s);
            }
            return;
        }
        for(int i=startIndex;i<s.size();i++) {
            if(isValid(s,startIndex,i)){     // 判断 [startIndex,i] 这个区间的子串是否合法
                s.insert(s.begin()+i+1,'.'); // 在i的后面插入一个逗点
                pointNum++;
                backtracking(s,i+2,pointNum);// 插入逗点之后下一个子串的起始位置为i+2
                pointNum--;                  // 回溯
                s.erase(s.begin()+i+1);      // 回溯删掉逗点
            }else break;                     //不合法，直接结束本层for循环
        }
    }
    vector<string> restoreIpAddresses(string s) {
        if(s.size() < 4 || s.size() > 12) return result; // 算是剪枝了
        backtracking(s,0,0);
        return result;
    }
};

代码007普通

打赏 收藏 海报 链接