hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Restore IP Addresses


  • Approach:

    1. The first hint for this problem to be solved is the length of an IP address. It is at least 4 digits and at most 12 digits, except the dots.

    2. That simply means we have to work only with the string of lengths 4 to 12. We can return an empty list for the string of the rest of the lengths.

    3. So we have a string maximum of 12 lengths.

    4. Now we need to divide it into 4 parts.

    5. Like we do generally, we will initiate 3 nested loops for the first 3 parts from the given string S. And will keep the remaining characters of S for the rest of the part.

    6. Now we will move to validate being a part of an IP address for those 4 parts.

    7. If they are validated then we will insert them into the resultant list.

    8. We will return the resultant list.


  • Time and Space Complexity:

      • Time Complexity: O(N^4)

      • Space Complexity: O(M*N)


Code [C++]

class Solution {

public:


int getNumber(string & s){

int number = 0;

for(int i=0; i<s.size(); i++){

number *= 10;

number += (s[i] - '0');

}

return number;

}


bool isValidIPAddress(vector<string>&octet, string & s){

s = "";

for(int i=0; i<4; i++){

if(octet[i].size() > 1 && octet[i][0] == '0') return false;

if(i > 0) s += '.';

if(getNumber(octet[i]) > 255) return false;

s += octet[i];

}

return true;

}


vector<string> restoreIpAddresses(string s) {

ios_base::sync_with_stdio(false);

cin.tie(NULL);

vector<string>answer;

int n = s.size();

if(n < 4 || n > 12) return answer;


vector<string>octet(4, "");

for(int i=0; i<n-3 && octet[0].size() <= 3; i++){

octet[0] += s[i];

for(int j=i+1; j<n-2 && octet[1].size() <= 3; j++){

octet[1] += s[j];

for(int l=j+1; l<n-1 && octet[2].size() <= 3; l++){

octet[2] += s[l]; octet[3] = s.substr(l+1, n-(l+1));

if(octet[3].size() > 3) continue;

string ret = "";

if(isValidIPAddress(octet, ret)){

answer.push_back(ret);

}

}

octet[2].clear();

}

octet[1].clear();

}

return answer;

}

};