LeetCode 468. Validate IP Address

September 22, 2020

We can solve this with string parsing in $O(n)$ time.

Should we use string parsing or regular expressions?

I'm going to use string parsing for the IPv4 check since the $x \leq 255$ cap is harder with a regex.

And I'm going to use regexes for the IPv6 check since that format is very compatible with regular expressions.

import re
import unittest

class Test(unittest.TestCase):

    def setUp(self):
        self.s = Solution()

    def test_examples(self):
        self.assertEqual(self.s.validIPAddress("172.16.254.1"), "IPv4")
        self.assertEqual(self.s.validIPAddress("2001:0db8:85a3:0:0:8A2E:0370:7334"), "IPv6")
        self.assertEqual(self.s.validIPAddress("256.256.256.256"), "Neither")
        self.assertEqual(self.s.validIPAddress("2001:0db8:85a3:0:0:8A2E:0370:7334:"), "Neither")
        self.assertEqual(self.s.validIPAddress("1e1.4.5.6"), "Neither")

    def test_empty(self):
        self.assertEqual(self.s.validIPAddress(""), "Neither")

    def test_leading_zero(self):
        self.assertEqual(self.s.validIPAddress("0.1.1.1"), "IPv4")
        self.assertEqual(self.s.validIPAddress("1.0.1.1"), "IPv4")
        self.assertEqual(self.s.validIPAddress("1.1.01.1"), "Neither")

class Solution:

    def __init__(self):
        self.ipv6 = re.compile(r"^([0-9a-fA-F]{1,4}:){8}$")

    def validIPAddress(self, IP: str) -> str:
        # Add another ':' so our regex can be simpler
        if self.ipv6.match(IP + ":"):
            return "IPv6"
        # Do IPv4 checking
        parts = IP.split(".")
        # Must have exactly 4 parts
        if len(parts) != 4:
            return "Neither"
        for p in parts:
            # A part must be of length 1-3 and not have a leading 0
            if not p or len(p) > 3 or len(p) > 1 and p[0] == "0":
                return "Neither"
            # A part can only contain digits
            if set(p) - set("0123456789"):
                return "Neither"
            # A part must be less than or equal to 255
            if int(p) > 255:
                return "Neither"
        return "IPv4"

if __name__ == "__main__":
    unittest.main()