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=225int 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+2pointNum--; // 回溯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+2pointNum--; // 回溯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;}
};参考和推荐文章、视频：
代码随想录 (programmercarl.com)
https://www.programmercarl.com/0093.%E5%A4%8D%E5%8E%9FIP%E5%9C%B0%E5%9D%80.html回溯算法如何分割字符串并判断是合法IP？| LeetCode：93.复原IP地址_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1XP4y1U73i/?spm_id_from=333.788&vd_source=a934d7fc6f47698a29dac90a922ba5a3