diff options
Diffstat (limited to 'restore_ip_addr.py')
-rw-r--r-- | restore_ip_addr.py | 51 |
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")) |