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"]
Table of Contents
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;
}