Validate an IP Address

You are given a string str in the form of an IPv4 Address. Your task is to validate an IPv4 Address, if it is valid return true otherwise return false.

IPv4 addresses are canonically represented in dot-decimal notation, which consists of four decimal numbers, each ranging from 0 to 255, separated by dots, e.g., 172.16.254.1

A valid IPv4 Address is of the form x1.x2.x3.x4 where 0 <= (x1, x2, x3, x4) <= 255. Thus, we can write the generalized form of an IPv4 address as (0-255).(0-255).(0-255).(0-255)

Note: Here we are considering numbers only from 0 to 255 and any additional leading zeroes will be considered invalid.

Examples :

Input: str = 222.111.111.111
Output: true
Explanation: Here, the IPv4 address is as per the criteria mentioned and also all four decimal numbers lies in the mentioned range.

Input: str = 5555..555
Output: false
Explanation: 5555..555 is not a valid. IPv4 address, as the middle two portions are missing.

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)

Constraints:
1<=str.length() <=15

Approach 01:

#include <string>
using namespace std;

class Solution {
public:
    int isValid(string s) {
        int dotCount = 0;  // Counter for valid segments separated by dots
        string currentSegment = "";  // To accumulate characters for each segment
        int strLength = s.size();  // Length of the input string

        for (int i = 0; i < strLength; i++) {
            if (s[i] == '.') {
                // Convert the accumulated segment to an integer
                int segmentValue = stoi(currentSegment);

                // Check if the segment value is within the valid range
                if (segmentValue >= 0 && segmentValue <= 255) {
                    dotCount++;  // Increment the count of valid segments
                    currentSegment = "";  // Reset for the next segment
                }
            } else {
                // Append character to the current segment
                currentSegment += s[i];
            }
        }

        // Check the last segment after the loop
        if (dotCount == 3) {
            int lastSegmentValue = stoi(currentSegment);

            // Validate the last segment value
            if (lastSegmentValue >= 0 && lastSegmentValue <= 255) {
                dotCount++;
            }
        }

        // Return 1 if there are exactly 4 valid segments, else return 0
        return (dotCount == 4) ? 1 : 0;
    }
};

class Solution:
    def isValid(self, s: str) -> int:
        dotCount = 0  # Counter for valid segments separated by dots
        currentSegment = ""  # To accumulate characters for each segment

        # Iterate through each character in the string
        for char in s:
            if char == '.':
                # Convert the accumulated segment to an integer
                segmentValue = int(currentSegment) if currentSegment else 0

                # Check if the segment value is within the valid range
                if 0 <= segmentValue <= 255:
                    dotCount += 1  # Increment the count of valid segments
                    currentSegment = ""  # Reset for the next segment
            else:
                # Append character to the current segment
                currentSegment += char

        # Check the last segment after the loop
        if dotCount == 3:
            lastSegmentValue = int(currentSegment) if currentSegment else 0

            # Validate the last segment value
            if 0 <= lastSegmentValue <= 255:
                dotCount += 1

        # Return 1 if there are exactly 4 valid segments, else return 0
        return 1 if dotCount == 4 else 0

Time Complexity

• Iterating Through the String:

  We iterate through the input string s once, which takes \( O(n) \) time, where \( n \) is the length of the string.

• Conversion to Integer:

  The conversion of string segments to integers using stoi is \( O(k) \), where \( k \) is the length of the segment. In the worst case, \( k \) is small and does not affect the overall time complexity significantly.

• Overall Time Complexity:

  The overall time complexity is \( O(n) \), dominated by the single pass through the string.

Space Complexity

• Auxiliary Space:

  We use a few variables such as dotCount, currentSegment, and strLength, which take \( O(1) \) space. The space used to store currentSegment is proportional to the length of the segment being processed, but this is still \( O(n) \) in total as it is part of the input string.

• Overall Space Complexity:

  The overall space complexity is \( O(n) \) due to the storage required for currentSegment.