93. Restore IP Addresses

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

Example:

Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

Solution

Approach 1: Recursion.

Code (Python)

Approach 1:

Code (C++)

Approach 1:

class Solution {
private:
    vector<string> IPs;
    void doRestoreIpAddresses(string s, int head, int level, string buf) {
        if (head >= s.size() || level == 4)
        {
            if (head == s.size() && level == 4)
                IPs.push_back(buf.substr(0, buf.size() - 1));
            return;
        }
        doRestoreIpAddresses(s, head + 1, level + 1, buf + s[head] + '.');
        if (s[head] == '0')
            return;
        if (head < s.size() - 1)
            doRestoreIpAddresses(s, head + 2, level + 1, buf + s.substr(head, 2) + '.');
        if (head < s.size() - 2 &&
            (s[head] < '2' ||
             s[head] == '2' && s[head+1] < '5' ||
             s[head] == '2' && s[head+1] == '5' && s[head+2] <= '5'))
            doRestoreIpAddresses(s, head + 3, level + 1, buf + s.substr(head, 3) + '.');
    }
public:
    vector<string> restoreIpAddresses(string s) {
        doRestoreIpAddresses(s, 0, 0, "");
        return IPs;
    }
};