Leetcode Restore IP Addresses problem solution YASH PAL, 31 July 2024 In this Leetcode Restore IP Addresses problem solution, we have given a string s containing only digits, return all possible valid IP addresses that can be obtained from s. You can return them in any order.A valid IP address consists of exactly four integers, each integer is between 0 and 255, separated by single dots, and cannot have leading zeros. For example, “0.1.2.201” and “192.168.1.1” are valid IP addresses and “0.011.255.245”, “192.168.1.312” and “192.168@1.1” are invalid IP addresses. 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; } coding problems solutions