复原IP地址(力扣93)

有了上一道题分割字符串的基础，这道题理解起来就会容易很多。相同的思想我就不再赘述，在这里我就说明一下此题额外需要注意的点。首先是终止条件如何确定，上一题我们递归到超过字符串长度时，则说明字符串已经分割完毕，而这道题根据题意，相当与用‘.’来分割字符串，且出现三个点时就可以结束递归了，那么我们需要一个变量来记录点的个数。另外，在我们判断分割出来的子串是否合法时，最后出现的子串可能为空串，就是说第三个点之后没有数字了。那么我么单独写一个判断来处理这种特殊情况。这是一些注意的重点，其他细节比较好懂，大家可以结合我下面的代码及详细注释理解此题。

代码及详细注释如下：

class Solution {
public:vector<string> result;//存放有效IP地址bool isValid(string& s,int start,int end){//空串的判断特殊处理if (start > end) {return false;}//一般情况if(s[start] == '0' && start != end){return false;}int sum = 0;for(int i = start;i <= end;i++){sum = sum * 10 + (s[i] - '0');}if(sum > 255) return false;return true;}void backtracking(string& s,int startIndex,int pointNum){//终止条件if(pointNum == 3){//最后一段子串要记得处理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)){s.insert(s.begin() + i + 1,'.');//插入点，表示分割pointNum++;backtracking(s,i + 2,pointNum);//递归分割其余子串//回溯pointNum--;s.erase(s.begin() + i + 1);}else break;}return;}vector<string> restoreIpAddresses(string s) {if(s.size() < 4 || s.size() > 12){return result;}backtracking(s,0,0);return result;}
};