# 93 - Restore IP Addresses

解法一 - Backtracking

這題的核心就是要放入 4 個 dot，而且放完之後隔出來的 4 個數字都要在 0-255 之間。所以很直覺就會想要用 backtracking 來做，接下來讓我們列一下幾個重點：

1. 怎麼判斷終止條件？放完 4 個點就可以終止了，所以可以傳給 backtrack 函式一個待放點數

2. 怎麼判斷要不要繼續往回走？看目前這個點隔出來的數字是否在 0-255 之間

3. 怎麼儲存中間狀態？用 string 表示就好

這題還有一點難在 string 的處理，不過還是可以實作出來：

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        string tmp;

        helper(s, res, tmp, 3, 0);

        return res;
    }

private:
    void helper(string& s, vector<string>& res, string& tmp, int dots, int pos) {
        if(dots == 0) {
            if(isValidChunk(s, pos, s.length())) {
                string validAdd = tmp;
                validAdd += s.substr(pos, s.length()-pos);
                res.push_back(validAdd);
                return;
            }
            else
                return;
        }
        else {
            for(int i=pos+1; i<s.length(); i++) {
                if(!isValidChunk(s, pos, i))
                    continue;

                string store = tmp;
                tmp += s.substr(pos, i-pos);
                tmp += ".";
                helper(s, res, tmp, dots-1, i);
                tmp = store;
            }
        }
    }

    bool isValidChunk(string s, int start, int end) {
        if(end-start > 3) return false;

        string sub = s.substr(start, end-start);
        // Prevent IP chunk such as "010", "00", etc.
        if(sub.length() > 1 && sub[0] == '0') return false;

        int num = stoi(sub);
        return num >=0 && num <= 255;
    }
};

解法二 - 枚舉所有可能的 chunk size

這個解法太炫了，直觀又好寫，趕快記一下：

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        string ans;

        for (int a=1; a<=3; a++)
        for (int b=1; b<=3; b++)
        for (int c=1; c<=3; c++)
        for (int d=1; d<=3; d++)
            if (a+b+c+d == s.length()) {
                int A = stoi(s.substr(0, a));
                int B = stoi(s.substr(a, b));
                int C = stoi(s.substr(a+b, c));
                int D = stoi(s.substr(a+b+c, d));
                if (A<=255 && B<=255 && C<=255 && D<=255)
                    if ( (ans=to_string(A)+"."+to_string(B)+"."+to_string(C)+"."+to_string(D)).length() == s.length()+3)
                        res.push_back(ans);
            }    

        return res;
    }
};