Restore IP Addresses

 dfs
class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        string ip;
        restoreIpAddressRe(s, res, ip, 0, 0);
        return res;
    }
    void restoreIpAddressRe(string &s, vector<string> &res, string &ip, int deep, int start)
    {
        if (deep == 4 && start == s.size())
            res.push_back(ip);
        if (deep == 4) return;
       
        int num = 0, origSize = ip.size();
        if (origSize != 0) ip.push_back('.');
        for (int i = start; i < s.size(); ++i)
        {
            num = num * 10 + s[i] - '0';
            if (num > 255) break;
            ip.push_back(s[i]);
            restoreIpAddressRe(s, res, ip, deep + 1, i + 1);
            if (num == 0) break;//not allow leading 0
        }
        ip.resize(origSize);
    }
};

//another flavor
class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> result;
        string ip; // save temporary result in processing
        dfs(s, 0, 0, ip, result);
        return result;       
    }
    void dfs(string s, size_t start, size_t step, string ip, vector<string> &result) {
        if (start == s.size() && step == 4) {  // find a possible result
            ip.resize(ip.size() - 1);
            result.push_back(ip);
            return;
        }

        // since each part of IP address is in 0..255, the length will not more than 3, and not less than 1 as well.
        if (s.size() - start > (4 - step) * 3)
            return;  // optimize, the length of rest part of s string should not more than 3 * remaining part count need to split.
        if (s.size() - start < (4 - step))
            return;  // optimize, the length of rest part of s string should not less than 1 * remaining part count need to split.

        int num = 0;
        for (size_t i = start; i < start + 3; i++) {
            num = num * 10 + (s[i] - '0');

            if (num <= 255) {  // current split is valid, go to next recursion.
                ip += s[i];
                dfs(s, i + 1, step + 1, ip + '.', result);
            }
            if (num == 0) break;  // single 0 is allowed, but '01' is forbidden.
        }
    }
};