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
Problem : 93. Restore IP Addresses
Problem Link : leetcode.com/problems/restore-ip-addresses/
Companies Asked : Yahoo, Amazon, Tiktok, Facebook, Microsoft, ByteDance, Arista Networks
Approach:
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.
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.
So we have a string maximum of 12 lengths.
Now we need to divide it into 4 parts.
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.
Now we will move to validate being a part of an IP address for those 4 parts.
If they are validated then we will insert them into the resultant list.
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;
}
};