复原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;
    }
};