aboutsummaryrefslogtreecommitdiff
path: root/restore_ip_addr.py
diff options
context:
space:
mode:
Diffstat (limited to 'restore_ip_addr.py')
-rw-r--r--restore_ip_addr.py51
1 files changed, 51 insertions, 0 deletions
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"))