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;
    
}