Leetcode：93. 复原 IP 地址（C++）

问题描述：

实现代码与解析：

回溯：

原理思路：

问题描述：

有效 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"]

实现代码与解析：

回溯：

class Solution {
public:vector<string> result;//记录所有结果vector<string> path;//记录ip每一段//判断切割出的字符串是否合法bool isValid(string s){//开头不为0且非单个字符if(s[0]=='0'&&s.size()!=1){return false;}int num=0;//不在0~255之间for(int i=0;i<s.size();i++){if(s[i]<'0'||s[i]>'9'){return false;}num=num*10+(s[i]-'0');if(num>255){return false;}}return true;        }//回溯法void backtracking(string s,int startIndex){//已经找到了4个片段if(path.size()==4){//未遍历所有字符，不符合条件，返回if(startIndex!=s.size()) return;//接收结果result.push_back(path[0] + '.' + path[1] + '.' + path[2] + '.' + path[3]);return;}for(int i=startIndex;i<startIndex+3&&i<s.size();i++)//最多取3个数，且不超过字符串大小{string str=s.substr(startIndex,i-startIndex+1);//截取的片段，左开右闭//判断是否合法，若合法if(isValid(str)){path.push_back(str);//处理backtracking(s,i+1);//递归path.pop_back();//回溯}else break;}return;}vector<string> restoreIpAddresses(string s) {backtracking(s,0);return result;}
};

原理思路：

其实还是切割问题，与上一题Leetcode：131. 分割回文串（C++）_Cosmoshhhyyy的博客-CSDN博客相同只不过是把切割片段换成了"."分割而已。

1、首先要写一个判断片段是否符合条件的函数，第一个字符不能为零且整个片段表示的数大小不超过255，也不能出现非法字符。这里可以不用判断字符个数是否大于3个，我们在循环的时候控制不要超过就可以了，还能达到剪枝的效果。

 //判断切割出的字符串是否合法
bool isValid(string s)
{//开头不为0且非单个字符if(s[0]=='0'&&s.size()!=1){return false;}int num=0;//不在0~255之间for(int i=0;i<s.size();i++){if(s[i]<'0'||s[i]>'9'){return false;}num=num*10+(s[i]-'0');if(num>255){return false;}}return true;        
}

2、然后写递归函数，终止条件就是已经切好了4个片段，若4个片段把所有字符都切了就将此结果按格式放入result数组中后返回，反之则直接返回。

//已经找到了4个片段
if(path.size()==4)
{//未遍历所有字符，不符合条件，返回if(startIndex!=s.size()) return;//接收结果result.push_back(path[0] + '.' + path[1] + '.' + path[2] + '.' + path[3]);return;
}

3、最后就是递归逻辑，循环控制最多取三个且不超过字符串大小，然后截取字符串，判断是否合法，不合法就直接break此层循环，因为这次循环截取的不合法，则后面截取的一定也不合法，若合法就开始递归和回溯流程，和其他回溯题相同

for(int i=startIndex;i<startIndex+3&&i<s.size();i++)//最多取3个数，且不超过字符串大小
{string str=s.substr(startIndex,i-startIndex+1);//截取的片段，左开右闭//判断是否合法，若合法if(isValid(str)){path.push_back(str);//处理backtracking(s,i+1);//递归path.pop_back();//回溯}
}

同样给大家一个流程图，方便大家理解。