[力扣题解]93. 复原 IP 地址

题目：93. 复原 IP 地址

思路

回溯法；
特别的是，用pointNum来记录.的数量，并且没有创建path，而是直接在原来的strings中插入.；
同时，在判断子串合法性的时候，0是合法的，01、00是不合法的；

代码

Method 1


class Solution {
public:

    vector<string> result; //

    void backtracking(string& s, int startIndex, int pointNum)
    {
        int i;
        if(pointNum == 3)
        {
            string temp1 = s.substr(startIndex, s.size()-startIndex);
            if(isValid(temp1))
            {
                result.push_back(s);
            }
            return;
        }
        for(i = startIndex; i < s.size(); i++)
        {
            // 判断子区间[startIndex, i]是否合法ß
            string temp2 = s.substr(startIndex, i-startIndex+1);
            if(isValid(temp2))
            {
                s.insert(s.begin()+i+1, '.'); //你为什么要加一个s.begin()
                // pointNum++;
                backtracking(s, i+2, pointNum+1);
                // pointNum--;
                s.erase(s.begin()+i+1);
            }
            // 不合法, 直接结束
            else
            {
                break;
            }
        }
    }
    // 使用 istringstream
    bool isValid(const string& s)
    {
        // 为空也不行
        if(s.empty())
        {
            return false;
        }
        int num;
        istringstream ss(s);
        ss >> num;
        // 0 <= num <= 255
        if(!(num >= 0 && num <= 255))
        {
            return false;
        }
        // 00 也不可以
        if(s.size() > 1 && s[0] == '0')
        {   
            return false;
        }
        return true;
    }
    
    vector<string> restoreIpAddresses(string s) 
    {
        result.clear();
        if(s.size() < 4 || s.size() > 12)
        {
            return result;
        }
        backtracking(s, 0, 0);
        return result;
    }
};

回溯pointNum用这个：backtracking(s, i+2, pointNum+1);

Method 2

class Solution {
public:

    vector<string> result; //

    void backtracking(string& s, int startIndex, int pointNum)
    {
        int i;
        if(pointNum == 3)
        {
            string temp1 = s.substr(startIndex, s.size()-startIndex);
            if(isValid(temp1))
            {
                result.push_back(s);
            }
            return;
        }
        for(i = startIndex; i < s.size(); i++)
        {
            // 判断子区间[startIndex, i]是否合法ß
            string temp2 = s.substr(startIndex, i-startIndex+1);
            if(isValid(temp2))
            {
                s.insert(s.begin()+i+1, '.'); //你为什么要加一个s.begin()
                pointNum++;
                backtracking(s, i+2, pointNum);
                pointNum--;
                s.erase(s.begin()+i+1);
            }
            // 不合法, 直接结束
            else
            {
                break;
            }
        }
    }
    // 使用 istringstream
    bool isValid(const string& s)
    {
        // 为空也不行
        if(s.empty())
        {
            return false;
        }
        int num;
        istringstream ss(s);
        ss >> num;
        // 0 <= num <= 255
        if(!(num >= 0 && num <= 255))
        {
            return false;
        }
        // 00 也不可以
        if(s.size() > 1 && s[0] == '0')
        {   
            return false;
        }
        return true;
    }
    
    vector<string> restoreIpAddresses(string s) 
    {
        result.clear();
        if(s.size() < 4 || s.size() > 12)
        {
            return result;
        }
        backtracking(s, 0, 0);
        return result;
    }
};

回溯pointNum用这个：

pointNum++;
pointNum--;

Method 3

类似于C的写法，基础方法，求出string代表的int；


    bool isValid(const string& s, int start, int end)
    {
        int i = 0;
        int num = 0;
        // 一直喜欢用各种奇奇怪怪函数的carl怎么没借助C++专门的工具?
        if(start > end)
        {
            return false;
        }
        // '0' 开头的数字不合法, 不包括数字'0'
        if(s[start] == '0' && start != end)
        {
            return false;
        }
        for(i = start; i <= end; i++)
        {
            // 遇到非数字字符不合法
            // if(!(s[i] >= 0 && s[i] <= 9))
            if(s[i] > '9' || s[i] < '0')
            {
                return false;
            }
            num = num * 10 + (s[i] - '0');
            // 如果大于255, 不合法
            if(num > 255)
            {
                return false;
            }
        }
        return true;
    }