Restore IP Addresses Problem Solution

Restore IP Addresses Problem: A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.

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

Restore IP Addresses Problem Solution

Problem Solution In Python

patterns = map(''.join, product(*[('(.)', '([^0].)', '(1..|2[0-4].|25[0-5])')] * 4))

class Solution:
  def restoreIpAddresses(self, s: str) -> List[str]:
    return ('.'.join(m.groups()) for m in (re.fullmatch(p, s) for p in patterns) if m)

Problem Solution In Java

class Solution {
    List<String> res = new ArrayList<>(); 
    public List<String> restoreIpAddresses(String s) {
        List<String> curr = new ArrayList<>(); 
        helper(s, 0, curr); 
        return res; 
    }
    public void helper(String s, int start, List<String> curr) { 
        if(curr.size() == 4) {
            if (start == s.length()) {
                res.add(curr.get(0) + "." +curr.get(1) + "." + curr.get(2) + "." + curr.get(3)); 
            }
            return; 
        } 
        for(int i=start; i<s.length(); i++) {
            if(i != start && s.charAt(start) == '0') break; 
            if(Integer.valueOf(s.substring(start,i+1)) > 255) break; 
            curr.add(s.substring(start,i+1)); 
            helper(s, i+1, curr);
            curr.remove(curr.size()-1); 
        }        
    }
}

Problem Solution In C++

class Solution {
public:
    vector<string> restoreIpAddresses(string s)
    {
        vector<string> res;
        if (s.size()<4 || s.size()>12) return res;
        for (int i=1; i<s.size()-2; i++)
            for (int j=i+1; j<s.size()-1; j++)
                for (int k=j+1; k<s.size(); k++)
                {
                    int num1, num2, num3, num4;
                    if (s[0]=='0' && i>1) continue;
                    else num1 = string2int(s.substr(0, i));
                    if (s[i]=='0' && j-i>1) continue;
                    else num2 = string2int(s.substr(i, j-i));
                    if (s[j]=='0' && k-j>1) continue;
                    else num3 = string2int(s.substr(j, k-j));
                    if (s[k]=='0' && s.size()-k>1) continue;
                    else num4 = string2int(s.substr(k));

                    if (num1<256 && num2<256 && num3<256 && num4<256)
                    {
                        string ss = s.substr(0, i)+'.'+s.substr(i, j-i)+'.'+s.substr(j, k-j)+'.'+s.substr(k);
                        res.push_back(ss);
                    }
                }
        return res;
    }

    int string2int(string s)
    {
        int res=0;
        for (int i=0; i<s.size(); i++)
            res = 10*res + s[i]-'0';
        return res;
    }
};

Problem Solution In C

char res[1000][20];
char ip[4][6];
int getNum(char *s, int start, int end) {
    if (end - start > 3) {
        return 300;
    }
    char tmp = s[end];
    s[end] = 0;
    int num = atoi(&s[start]);
    s[end] = tmp;
    return num;
}
void getIp(char *s, int *returnSize, int level, int startIndex) {
    if (startIndex >= strlen(s)) {
        return;
    }
    if (level == 3) {
        int num = getNum(s, startIndex, strlen(s));
        if (num > 255 || (s[startIndex] == '0' && startIndex < strlen(s) - 1)) {
            return;
        }else {
            sprintf(ip[level], "%s", &s[startIndex]);
            sprintf(res[*returnSize],"%s.%s.%s.%s", ip[0], ip[1], ip[2], ip[3]);
            (*returnSize)++;
        }
        return;
    }else {
        
        sprintf(ip[level], "%c", s[startIndex]);
        getIp(s, returnSize, level + 1, startIndex + 1);
        if (startIndex < strlen(s) - 2 && s[startIndex] != '0') {
            sprintf(ip[level], "%c%c", s[startIndex], s[startIndex + 1]);
            getIp(s, returnSize, level + 1, startIndex + 2);
        }
        if (startIndex < strlen(s) - 3 && s[startIndex] != '0') {
            int num = getNum(s, startIndex, startIndex + 3);
            if (num <= 255) {
                sprintf(ip[level], "%c%c%c", s[startIndex], s[startIndex + 1], s[startIndex + 2]);
                getIp(s, returnSize, level + 1, startIndex + 3);
            }

        }
    }
    
    
}
char ** restoreIpAddresses(char * s, int* returnSize){
    *returnSize = 0;
    getIp(s, returnSize, 0, 0);
    char **r = (char **)malloc((sizeof(char *))*5000);
    for (int i = 0; i < *returnSize; i++) {
        r[i] = (char *)malloc(25);
        strcpy(r[i], res[i]);
    }
    return r;
    
}


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment