Restore IP Addresses

题目：

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

分析：

这道题目有几个隐藏的考察点，

(1) 对substring的取出是否熟练

(2) 会不会string转化为int （stoi）

(3) 处理 "11111"容易，但是有没有考虑到"00000"这种变态情况？

(4) 按照section做，还是按照.做？方法1和方法2什么区别？

针对解法1，需要注意下列具体环节：

(1) 取sub str的方法是

string subIP(s.begin() + start, s.begin() + i + 1);
//or
string subIP = s.substr(start, i - start + 1);

(2) 在instance,size() == 4之后，判断退出的条件为start != s.size();表示有没有到结尾

(3) 在for循环里面加入i <= start + 3可以减少不必要的loop

解法1：

class Solution {
public:
    /**
     * @param s the IP string
     * @return All possible valid IP addresses
     */
    bool isValid(string subIP) {
        if (subIP[0] == '0' && subIP.size() > 1) {
            return false;
        }
        int subIPnum = stoi(subIP);
        if (subIPnum > 255) {
            return false;
        }
        return true;
    }

    void dfs(string s, vector<string> instance, vector<string>& res, int start) {
        if (instance.size() == 4) {
            if (start != s.size() ) {
                return;
            }
            res.push_back(instance[0] + "." + instance[1] + "." + instance[2] + "." + instance[3]);
            return;
        }

        for (int i = start; i < s.size() && i <= start + 3; i++) {

            string subIP(s.begin() + start, s.begin() + i + 1);

            if (!isValid(subIP) ) {
                continue;
            }

            instance.push_back(subIP);
            dfs(s, instance, res, i + 1);
            instance.pop_back();
        }
    }

    vector<string> restoreIpAddresses(string& s) {
        // Write your code here
        if (s.size() < 4 || s.size() > 12) {
            return vector<string>();
        }

        vector<string> res;
        vector<string> instance;

        dfs(s, instance, res, 0);
        return res;
    }
};

解法2：

class Solution {
public:
    /**
     * @param s the IP string
     * @return All possible valid IP addresses
     */

    string toIPStirng(vector<int> instance, string s) {

        // return to_string(instance[0]) + "." + to_string(instance[1]) + "." + to_string(instance[2]);

        string IP1 = s.substr(0, instance[0]);
        string IP2 = s.substr(instance[0], instance[1] - instance[0]);
        string IP3 = s.substr(instance[1], instance[2] - instance[1]);
        string IP4 = s.substr(instance[2], s.size() - instance[2]);

        return IP1 + "." + IP2 + "." + IP3 + "." + IP4;
    } 

    bool isValidIP(vector<int> instance, string s) {


        string subIP = s.substr(0, instance[0]);
        if (subIP.size() > 1 && subIP[0] == '0') {
            return false;
        }

        int numIP = 0;
        for (int i = 0; i < instance[0]; i++) {
            numIP *= 10;
            numIP += (s[i] - '0');
        }
        if (numIP > 255) {
            return false;
        }

        subIP = s.substr(instance[0], instance[1] - instance[0]);
        if (subIP.size() > 1 && subIP[0] == '0') {
            return false;
        }

        numIP = 0;
        for (int i = instance[0]; i < instance[1]; i++) {
            numIP *= 10;
            numIP += (s[i] - '0');
        }
        if (numIP > 255) {
            return false;
        }

        subIP = s.substr(instance[1], instance[2] - instance[1]);
        if (subIP.size() > 1 && subIP[0] == '0') {
            return false;
        }

        numIP = 0;
        for (int i = instance[1]; i < instance[2]; i++) {
            numIP *= 10;
            numIP += (s[i] - '0');
        }
        if (numIP > 255) {
            return false;
        }

        subIP = s.substr(instance[2], s.size() - instance[2]);
        if (subIP.size() > 1 && subIP[0] == '0') {
            return false;
        }

        numIP = 0;
        for (int i = instance[2]; i < s.size(); i++) {
            numIP *= 10;
            numIP += (s[i] - '0');
        }
        if (numIP > 255) {
            return false;
        }

        return true;
    } 

    void dfs(string s, vector<int> instance, vector<string>& res, int start) {

        if (instance.size() == 3) {
            if (isValidIP(instance, s) ) {
                res.push_back( toIPStirng(instance, s) );
            }
            return;
        }

        for (int i = start; i < s.size(); i++) {
            instance.push_back(i);
            dfs(s, instance, res, i + 1);
            instance.pop_back();
        }

    } 

    vector<string> restoreIpAddresses(string& s) {
        // Write your code here
        if (s.size() < 4 || s.size() > 12) {
            return vector<string>();
        }

        vector<string> res;
        vector<int> instance;

        dfs(s, instance, res, 1);
        return res;
    }
};