aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-01-10 13:16:58 +0100
committerJack Sangdahl <[email protected]>2025-01-10 13:16:58 +0100
commitfbd68b1d63c63150c6ea0e927668fe5f18293be7 (patch)
tree4f9f2572984754be36d2f73ee4a9c68b4e35e2af
parent3698398d290bdb4c94bd13046d16d96713b8111b (diff)
downloadleetcode-fbd68b1d63c63150c6ea0e927668fe5f18293be7.tar.gz
leetcode-fbd68b1d63c63150c6ea0e927668fe5f18293be7.zip
93. restore ip addresses
-rw-r--r--restore_ip_addr.c110
-rw-r--r--restore_ip_addr.py51
2 files changed, 104 insertions, 57 deletions
diff --git a/restore_ip_addr.c b/restore_ip_addr.c
index e814691..f967d4f 100644
--- a/restore_ip_addr.c
+++ b/restore_ip_addr.c
@@ -1,8 +1,5 @@
// 93. Restore IP Addresses
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-#define IN_RANGE(c, m, n) ((c) >= (m) && c <= (n))
+#include "leetcode.h"
/*
* a valid ip address consists of exactly 4 integers separated by single dots
@@ -12,63 +9,62 @@
* reordered or removed. return addresses in any order.
*/
-int isValidPart(char *s, int l) {
- switch (l) {
- case 1:
- return IN_RANGE(s[0], '0', '9');
- break;
- case 2:
- return IN_RANGE(s[0], '1', '9') && IN_RANGE(s[1], '0', '9');
- break;
- case 3:
- return (s[0] == '1' && IN_RANGE(s[1], '0', '9') &&
- IN_RANGE(s[2], '0', '9')) ||
- (s[0] == '2' &&
- (IN_RANGE(s[1], '0', '4') && IN_RANGE(s[2], '0', '9') ||
- s[1] == '5' && IN_RANGE(s[2], '0', '5')));
- break;
- default:
- return 0;
- }
-}
-
-char *getAddr(char *s, int l, int a, int b, int c) {
- if (isValidPart(s, a) && isValidPart(s + a, b - a) &&
- isValidPart(s + b, c - b) && isValidPart(s + c, l - c)) {
- char *addr = malloc(sizeof(char) * (l + 4));
- memcpy(addr, s, a);
- memcpy(addr + a + 1, s + a, b - a);
- memcpy(addr + b + 2, s + b, c - b);
- memcpy(addr + c + 3, s + c, l - c);
- addr[a] = addr[b + 1] = addr[c + 2] = '.';
- addr[l + 3] = '\0';
- return addr;
- } else
- return NULL;
-}
-
char **restoreIpAddresses(char *s, int *returnSize) {
+ int n = strlen(s), capacity = 0;
+ char **ans = NULL;
*returnSize = 0;
- int l = strlen(s), a, b, c;
- if (l < 4 || l > 12)
- return NULL;
- char **addrs = malloc(sizeof(char *) * ((l - 1) * (l - 2) * (l - 3) / 6)),
- *addr;
- for (a = 1; a < 4; a++) {
- if (a > l - 3 || a < l - 9)
- continue;
- for (b = a + 1; b < a + 4; b++) {
- if (b > l - 2 || b < l - 6)
- continue;
- for (c = b + 1; c < b + 4; c++) {
- if (c > l - 1 || c < l - 3)
- continue;
- if (addr = getAddr(s, l, a, b, c))
- addrs[(*returnSize)++] = addr;
+ for (int a = 1; a <= 3 && a + 2 < n && (1 == a || '0' != s[0]) &&
+ (a < 3 || 0 > memcmp(s, "256", 3));
+ ++a) {
+ for (int b = a + 1;
+ b <= a + 3 && b + 1 < n && (a + 1 == b || '0' != s[a]) &&
+ (b < a + 3 || 0 > memcmp(s + a, "256", 3));
+ ++b) {
+ for (int c = b + 1; c <= b + 3 && c < n && (b + 1 == c || '0' != s[b]) &&
+ (c < b + 3 || 0 > memcmp(s + b, "256", 3));
+ ++c) {
+ if (c + 3 >= n && (c + 1 == n || '0' != s[c]) &&
+ (n < c + 3 || 0 > memcmp(s + c, "256", 3))) {
+ if (*returnSize >= capacity) {
+ capacity = capacity ? capacity * 2 : 1;
+ ans = (char **)realloc(ans, capacity * sizeof(char *));
+ }
+ char *dest = (char *)malloc((n + 4) * sizeof(char));
+ memcpy(dest, s, a);
+ dest[a] = '.';
+ memcpy(dest + a + 1, s + a, b - a);
+ dest[b + 1] = '.';
+ memcpy(dest + b + 2, s + b, c - b);
+ dest[c + 2] = '.';
+ memcpy(dest + c + 3, s + c, n - c);
+ dest[n + 3] = '\0';
+ ans[(*returnSize)++] = dest;
+ }
}
}
}
- return addrs;
+ return ans;
}
-int main() { char s1[] = {"25525511135"}, s2[] = {"0000"}, s3[] = {"101023"}; }
+int main() {
+ char *s1 = "25525511135", *s2 = "0000", *s3 = "101023";
+ int rs1, rs2, rs3;
+ char **ria1 = restoreIpAddresses(s1, &rs1);
+ char **ria2 = restoreIpAddresses(s2, &rs2);
+ char **ria3 = restoreIpAddresses(s3, &rs3);
+ for (int i = 0; i < rs1; i++)
+ printf("%s ", ria1[i]); // expect: ["255.255.11.135","255.255.111.35"]
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%s ", ria2[i]); // expect: ["0.0.0.0"]
+ printf("\n");
+ for (int i = 0; i < rs3; i++)
+ printf(
+ "%s ",
+ ria3[i]); // expect:
+ // ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
+ printf("\n");
+ free(ria1);
+ free(ria2);
+ free(ria3);
+}
diff --git a/restore_ip_addr.py b/restore_ip_addr.py
new file mode 100644
index 0000000..3d1b178
--- /dev/null
+++ b/restore_ip_addr.py
@@ -0,0 +1,51 @@
+# 93. Restore IP Addresses
+
+"""
+a valid ip address consists of exactly 4 integers separated by single dots
+each integer is between 0 and 255 (inclusive) and cannot have leading 0's
+given: string 's' containing only digits, return all possible valid ip
+addresses that can be formed by insert dots into 's'. digits cannot be
+reordered or removed. return addresses in any order.
+"""
+
+
+class Solution(object):
+ def restoreIpAddresses(self, s):
+ """
+ :type s: str
+ :rtype: List[str]
+ """
+ ans = []
+ for a in range(1, 4):
+ for b in range(1, 4):
+ for c in range(1, 4):
+ d = len(s) - a - b - c
+ if (
+ 1 <= d <= 3
+ and (1 == a or "0" != s[0])
+ and (a != 3 or s[:a] <= "255")
+ and (1 == b or "0" != s[a])
+ and (b != 3 or s[a : a + b] <= "255")
+ and (1 == c or "0" != s[a + b])
+ and (c != 3 or s[a + b : a + b + c] <= "255")
+ and (1 == d or "0" != s[a + b + c])
+ and (d != 3 or s[a + b + c :] <= "255")
+ ):
+ ans.append(
+ ".".join(
+ [
+ s[0:a],
+ s[a : a + b],
+ s[a + b : a + b + c],
+ s[a + b + c :],
+ ]
+ )
+ )
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.restoreIpAddresses(s="25525511135"))
+ print(obj.restoreIpAddresses(s="0000"))
+ print(obj.restoreIpAddresses(s="101023"))