93-复原ip地址

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

提示：

• 1 <= s.length <= 20
• s 仅由数字组成

C++:

class Solution {
public:
    vector<string>ans;

    bool isip(const string&s,int begin,int end){
        if(begin>end) return false;
        if(s[begin]=='0'&&begin!=end) return false;
        int num=0;
        for (int i = begin; i <= end; ++i) {
            if(s[i]<'0'||s[i]>'9') return false;
            num=num*10+s[i]-'0';
            if(num>255) return false;
        }
        return true;
    }
    //直接把s添加到ans中,这样可以直接在s上进行插入和删除的操作,不用再一个一个添加字符进行处理
    void bt(string&s,int index,int pointn){ 
        //这里用小数点的个数来判断是否结束,分割成四段
        if(pointn==3){
            if(isip(s,index,s.size()-1)) ans.push_back(s);
            return;
        }
        for(int i=index;i<s.size();i++){
            if(isip(s,index,i)){
                s.insert(s.begin()+i+1,'.');
                pointn++;
                //插入了小数点，所以要+2
                bt(s,i+2,pointn);
                pointn--;
                //erase删除指定位置的小数点
                s.erase(s.begin() +i + 1);
            }
            else break;
        }
    }

    vector<string> restoreIpAddresses(string s) {
        bt(s,0,0);
        return ans;
    }
};