Validate IP Address

For each address, we split it into chunks delimited by a period. A valid address must have 4 chunks. Then, for each chunk, we will check whether it is the string representation of a number from 0 to 255.

We need to check that all the characters in the string are digits, and that there are no leading zeroes, and the string-to-int representation is in the range [0, 255].

function fitsOneByte(chunk):
    # Does this string chunk represent a number
    # from 0 to 255?

    # If it's empty string, return false.
    if chunk.length == 0:
        return false

    # If any character in the string isn't a
    # digit, return false.
    for i from 0 to chunk.length - 1:
        if chunk[i] < '0' OR chunk[i] > '9':
            return false

    # If the string has a leading zero and isn't
    # zero, return false.
    if chunk.length >= 2 AND chunk[0] == '0':
        return false

    # Return true if and only if parsing the
    # chunk as an integer is between 0 and 255.
    return 0 <= int(chunk) AND int(chunk) <= 255

function validate(address):
    # If the number of periods is not 3, then
    # it can't be an IP address.
    chunks = address.split('.')
    if chunks.length != 4:
        return false

    # Check that each chunk delimited by periods,
    # represents a number from 0-255.
    for chunk in chunks:
        if not fitsOneByte(chunk):
            return false

    return true

Note: If our library does not have the built-in "split" for strings, we could still write one as shown below.

We record seen characters into a buffer, and flush the buffer into our answer every time we see a delimiting character.

function split(string, delimiter):
    buffer = ""
    answer = []
    for character in string:
        if character == delimiter:
            answer.push(buffer)
            buffer = ""
        else:
            buffer += character

    answer.push(buffer)
    return answer

Computational Complexity

Say the given string is N characters. Our split operation takes O(N) time and O(N) space. Our fitsOneByte operation takes a linear amount of time and space for each chunk, and the sum of the chunks is the whole string.

Thus, the time complexity is O(N), and the space complexity is O(N).

Time Complexity: O(N), where N is the number of characters in ip. Our split operation takes O(N) time, and our fitsOneByte operation takes a linear amount of time for each chunk, and the sum of the chunks is the whole string.

Space Complexity: O(N), the space used when considering each part of the original string ip.