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”]

The solution for this problem can be done in 2 ways.
1. Iterative/Brute force approach
2. Recursive/DFS

But before we solve this, we need to consider below few points:

An IP address consists of four parts. Each part is of “0 to 255”. Hence a legal IP address can be obtained recursively. So every time we find a valid part, we go to the next part recursively.

We need to take care of below rules:
1. inputs less than 4 and greater than 12 will be thrown away
2. The value of each field cannot be greater than 255
3. There are exactly 4 fields
4. When the length of a field >= 2, it cannot start with 0.
5. the case of 0, 001, 010, 03 are illegal.

So the logic is as follows:

If the current character is not the last character, then if it is appended to the current existing data, the new value should not be greater than 255.

If the existing number of decimal points is less than 3, then consider adding a decimal point. Then start with the current character to start new part.

If the current data field is not 0, you can consider attaching this character directly to the current existing data field.

If the current character is the last character, If there are currently three decimal points, the current data field is not 0, and the current character is appended to the current data field, and the new value of the data field will not be greater than 255, you can consider doing this.
Otherwise, if there are currently two decimal points, the current data field is ended with a decimal point, and then the current character is used as the last data field to form a solution.

Otherwise the current branch fails

Solution in C++:

#include<iostream>
#include<string>
#include<vector>

using namespace std;


vector<string> restoreIpAddresses_iterative(string s) 
{
    vector<string> result;
    string partialIP;

    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 ( (partialIP=to_string(A)+"."+to_string(B)+"."+to_string(C)+"."+to_string(D)).length() == s.length()+3)
                                result.push_back(partialIP);
                        }    

    return result;
}


 bool isValid(string str)
 {
        
    if(str.length() == 0 || str.length() > 3) return false;
    if(str[0] == '0' && str.length() > 1) return false;
        
    int num = std::stoi(str);
    if(num >= 0 && num <= 255)
    {
        return true;
    }
    else
    {
        return false;
    }
}

   //s:         The input string
   //partialIP: Partial ip that is being constructed
   //result:       Result ip address
   //segment:   The index of traversal character
   
void restoreIpAddresses_helper_dfs(string s, string partialIP, vector<string>& result, int segment)
{

    if(segment == 4 && isValid(s))
    {
        result.push_back(partialIP + s);
        return;
    }
        
    for(int i = 1; i < 4 && (i < s.length()); i++)
    {
        string substr = s.substr(0, i);
        if(isValid(substr))
        {
            int strlen = s.length();
            restoreIpAddresses_helper_dfs(s.substr(i, strlen - i), partialIP + substr + '.' , result, segment + 1);
        }
            
    }
}

vector<string> restoreIpAddresses_DFS(string s) 
{
        
    vector<string> result;
    if(s.length() < 4 || s.length() > 12) return result;
    int strlen = s.length();
    
    restoreIpAddresses_helper_dfs(s, "", result, 1);
    
    return result;
}


int main()
{
    string str = "25525511135";
    //vector<string> result = restoreIpAddresses_iterative(str);
    vector<string> result = restoreIpAddresses_DFS(str);

    cout<<"\nThe IP address = "<<endl;
    
    for (int i = 0; i < result.size(); i++)
    {
        cout <<result[i] << endl;
    }
    cout<<endl;
}

Output:

The IP address =
255.255.11.135
255.255.111.35