93. 复原 IP 地址

93. 复原 IP 地址

class Solution {
public:
    bool isvalid(string& s,int start,int end)
    {
        //处理就三段数字的情况，最后一位是.
        if(start>end)return false;
        //处理开头为0的情况（除了单独一个0）
        if(s[start]=='0'&&start!=end)return false;
        //处理大小越界的情况
        int lastnum = 0;
        for(int i=start;i<=end;i++)
        {
            lastnum = lastnum*10 + s[i]-'0';
            if(lastnum>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;
        }
    }
    vector<string> restoreIpAddresses(string s) {
        backtracking(s,0,0);
        return result;
    }
    vector<string> result;
};