Restore IP Addresses

Restore IP AddressesAug 8 '12

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

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

This one is actually more tricky than it seems to be as it involves several corner cases.
DFS

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s.size() > 12 || s.size() < 4) return vector<string>();
        return getValidIP(s.c_str(), 0);
    }
    
    vector<string> getValidIP(const char *c, int n) {
        const char *head = c;
        if (n == 3) {
            int num = 0;
            while (*c != '\0') {
                num = num * 10 + *c - '0';
                ++c;
            }
            vector<string> ret;
            
            // last segment requirements
            // at least one digit and at most one leading zero
            if (c - head > 1 && *head == '0' || c == head) return ret;
            
            // segment number cannot exceed 255
            if (num <= 255) {
                string seg(head, c - head);
                ret.push_back(seg);
            }
            return ret;
        }
        int num = 0;
        vector<string> ret;
        for (int i = 0; i < 3; ++i) {
            // reaches end or digits exceed 3
            if (*c == '\0' || c - head > 2) break;
            
            num = num * 10 + *c - '0';
            
            // each segment can be at most 255
            if (num > 255) break;
            
            vector<string> rest = getValidIP(++c, n + 1);
            string add_seg(head, c - head);
            for (auto s : rest) {
                string address(add_seg);
                address += ".";
                address += s;
                ret.push_back(address);
            }
            
            // only one leading 0 allowed
            if (*(c - 1) == '0' && i == 0) break;
        }
        return ret;
    }
};