Vultr DocsLatest Content

Restore IP Addresses

Updated on 19 June, 2025
Restore IP Addresses header image

Problem Statement

In the realm of networking, a valid IPv4 address is defined by four integers separated by dots. Each of these integers can range from 0 to 255. Importantly, these integers should not contain any leading zeros unless the number itself is zero (for instance, "0.1.2.3" is valid but "01.1.2.3" is not).

Given a straightforward input string s composed only of digits, the challenge is to determine all conceivable valid IP addresses that can be fashioned by inserting dots in appropriate places within s. The complications include ensuring that no integers exceed 255, no section starts with a zero if it has more than one digit, and modifying the original order of characters in s is not permitted. The task requires generating each potential configuration that meets the definition of a valid IP address and returning them in any sequence.

This problem tests the ability to manipulate strings, understand constraints thoroughly, and efficiently handle multiple nested conditions in programming.

Examples

Example 1

Input:

s = "25525511135"

Output:

["255.255.11.135","255.255.111.35"]

Example 2

Input:

s = "0000"

Output:

["0.0.0.0"]

Example 3

Input:

s = "101023"

Output:

["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

Constraints

  • 1 <= s.length <= 20
  • s consists of digits only.

Approach and Intuition

To address the problem of generating all valid IP addresses from a string, a systematic approach involving the following steps can be employed:

  1. Initial Verification:

    • Check if the string is too short or too long to potentially form an IP address, specifically considering that the shortest IP address string is 4 digits (all zeros) and the longest is 12 digits (all 255). If s length is outside this range, it can dramatically reduce the number of computations by early exit.

  2. Backtracking Algorithm:

    • Utilize a recursive approach to try and fit each possible segment into the potential IP address. At each step, attempt to place a dot after 1, 2, or 3 digits and check if this forms a valid segment (0-255, no leading zeros unless the segment is '0').

  3. Checking Conditions:

    • For each segment considered, validate the segment:
      • It must not exceed the value 255.
      • It must not have leading zeros unless the segment is exactly '0'.

  4. Recursive Exploration:

    • On confirming a valid segment, recursively attempt to place the next dot, adjusting the position in the string and the part of the IP address being constructed.
    • If a segment is invalid, backtrack and try a different configuration.
    • Continue this until four valid segments are obtained or return to a previous step if the current path fails.

  5. Gather Results:

    • Each time four valid segments are constructed, combine them into a dot-separated string and add this to the list of results.

Given the constraints and provided examples, this recursive method (often implemented with backtracking) efficiently explores all potential combinations and adheres to the conditions for constructing valid IP addresses. This approach ensures that all configurations are considered without repeating or missing potential valid answers.

Solutions

  • C++
  • Java
  • C
  • JavaScript
  • Python
cpp 
class Solution {
    bool isValidSegment(const string& str, int offset, int len) {
        return len == 1 || 
               (str[offset] != '0' && 
                (len < 3 || str.substr(offset, len) <= "255"));
    }

public:
    vector<string> generateIPAddresses(string str) {
        vector<string> result;
        int strLength = str.length();
        for (int a = max(1, strLength - 9); a <= 3 && a <= strLength - 3; ++a) {
            if (!isValidSegment(str, 0, a)) {
                continue;
            }
            for (int b = max(1, strLength - a - 6);
                 b <= 3 && b <= strLength - a - 2; ++b) {
                if (!isValidSegment(str, a, b)) {
                    continue;
                }
                for (int c = max(1, strLength - a - b - 3);
                     c <= 3 && c <= strLength - a - b - 1; ++c) {
                    if (isValidSegment(str, a + b, c) &&
                        isValidSegment(str, a + b + c,
                                       strLength - a - b - c)) {
                        result.push_back(str.substr(0, a) + "." +
                                         str.substr(a, b) + "." +
                                         str.substr(a + b, c) + "." +
                                         str.substr(a + b + c));
                    }
                }
            }
        }
        return result;
    }
};

The provided C++ solution involves restoring valid IP addresses from a given string str that represents a sequence of digits. The solution defines a class named Solution with a method generateIPAddresses which returns all possible valid IP addresses.

Key Components of the Solution:

  • isValidSegment Function:

    • This helper function checks if a specific substring in str is a valid segment of an IP address. It considers a segment valid if it's either a single-digit, not starting with zero and is less than or equal to '255' when a multi-digit.

  • generateIPAddresses Function:

    • This function is designed to find and store valid IP addresses.
    • It starts with three nested loops, each specifying the length of one segment of the IP address, aiming to build a valid configuration.
    • The loops use the isValidSegment function to decide if a segment of the string being iterated over can be considered as a valid part of an IP address.
    • As the loops iterate, valid segments are concatenated with dots to form a plausible IP address, which is added to the result vector if all four parts meet the segment criteria.

Process to Retrieve IP Addresses:

  • Iterate over possible lengths for each IP address segment using nested loops, ensuring none of the segments start with zero unless the segment itself is zero, and no segment is longer than three characters unless it forms a valid part of the address.
  • Use conditions to check for bounds and valid parts, constructing the IP and storing it when a valid one is formed.
  • Return the vector containing the valid IP addresses once all possible combinations are examined.

The solution is efficient since it limits the range of each part's generation using logical truncations based on the remaining parts that need to be filled, avoiding unnecessary computations. This ensures that all possible valid IP addresses from the digit sequence are generated and checked for validity.

java 
class Solution {
    private boolean checkSegment(String input, int index, int segmentLength) {
        return (
            segmentLength == 1 ||
            (input.charAt(index) != '0' &&
            (segmentLength < 3 || input.substring(index, index + segmentLength).compareTo("255") <= 0))
        );
    }

    public List<String> generateIPs(String input) {
        List<String> result = new ArrayList<>();
        for (
            int len1 = Math.max(1, input.length() - 9);
            len1 <= 3 && len1 <= input.length() - 3;
            ++len1
        ) {
            if (!checkSegment(input, 0, len1)) {
                continue;
            }

            for (
                int len2 = Math.max(1, input.length() - len1 - 6);
                len2 <= 3 && len2 <= input.length() - len1 - 2;
                ++len2
            ) {
                if (!checkSegment(input, len1, len2)) {
                    continue;
                }
                for (
                    int len3 = Math.max(1, input.length() - len1 - len2 - 3);
                    len3 <= 3 && len3 <= input.length() - len1 - len2 - 1;
                    ++len3
                ) {
                    if (
                        checkSegment(input, len1 + len2, len3) &&
                        checkSegment(
                            input,
                            len1 + len2 + len3,
                            input.length() - len1 - len2 - len3
                        )
                    ) {
                        result.add(
                            String.join(
                                ".",
                                input.substring(0, len1),
                                input.substring(len1, len1 + len2),
                                input.substring(len1 + len2, len1 + len2 + len3),
                                input.substring(len1 + len2 + len3)
                            )
                        );
                    }
                }
            }
        }
        return result;
    }
}

This Java solution efficiently handles the task of restoring IP addresses from a string of digits. The main method generateIPs takes a string input and returns all possible valid IPv4 addresses by placing dots appropriately.

  • The process involves generating all possible combinations of the string split into four parts, ensuring each part is a valid segment of an IP address.

  • The helper function, checkSegment, verifies if a particular segment of the string can be a valid part of an IP address. It ensures:

    • The segment's length is appropriate (1 to 3 characters).
    • The segment doesn't start with zero unless it is zero itself.
    • The numeric value of the segment doesn't exceed 255.

  • The main method uses nested loops to attempt every possible way of splitting the string into four parts, based on the constraints given by IP address formatting:

    • The first loop determines the end of the first part.
    • The second loop figures out the end of the second part.
    • The third loop helps to find the end of the third part.
    • The remainder of the string after the first three parts constitutes the fourth part.

  • For each possible split, it checks if all four parts are valid using checkSegment. If so, it constructs a valid IP address and adds it to the result list.

This solution ensures efficiency by only processing feasible splits and by checking validity upfront before forming the IP address string. This method generates all valid IPs, adding potential solutions by leveraging proper segment checks and controlled iteration using string manipulation techniques.

c 
int isValidSegment(char *str, int pos, int sz) {
    if (sz == 1) return 1;
    if (str[pos] == '0') return 0;
    if (sz > 2) {
        char segment[4];
        strncpy(segment, str + pos, sz);
        segment[sz] = '\0';
        if (atoi(segment) > 255) return 0;
    }
    return 1;
}

char **generateIPs(char *str, int *count) {
    char **resultArray = malloc(0);
    *count = 0;
    int strLen = strlen(str);
    for (int first = strLen - 9 > 1 ? strLen - 9 : 1;
         first <= 3 && first <= strLen - 3; ++first) {
        if (!isValidSegment(str, 0, first)) continue;
        for (int second = strLen - first - 6 > 1 ? strLen - first - 6 : 1;
             second <= 3 && second <= strLen - first - 2; ++second) {
            if (!isValidSegment(str, first, second)) continue;
            for (int third = strLen - first - second - 3 > 1
                                ? strLen - first - second - 3
                                : 1;
                 third <= 3 && third <= strLen - first - second - 1; ++third) {
                if (isValidSegment(str, first + second, third) &&
                    isValidSegment(str, first + second + third, strLen - first - second - third)) {
                    char *ip = malloc(16);
                    sprintf(ip, "%.*s.%.*s.%.*s.%.*s", first, str, second, str + first,
                            third, str + first + second, strLen - first - second - third,
                            str + first + second + third);
                    resultArray = realloc(resultArray, (*count + 1) * sizeof(char *));
                    resultArray[(*count)++] = ip;
                }
            }
        }
    }
    return resultArray;
}

The provided C code defines functions to generate valid IP addresses from a given string of digits by splitting the string into segments and checking the validity of each segment according to IP address rules.

  • isValidSegment(char *str, int pos, int sz): This function checks if the substring starting at position pos with size sz is a valid segment of an IP address. It checks for single digit segments, fragmentation of the leading zeros, and numerical value not exceeding 255.

  • generateIPs(char *str, int *count): This function attempts to create all possible valid IP addresses by exhaustively trying different splits of the input string str. It uses nested loops to divide the string into four parts, where each split position is governed by the rules of IP segmentation (maximum 3 digits and total less than or equal to 255). For each valid segmentation, it formats the substrings into a dotted IP address format, reallocates memory to store the new IP address in the result array, and updates the count.

Follow these steps to utilize the provided functions:

  1. Call generateIPs with the string of digits and a pointer to an integer to store the count of valid IPs generated.
  2. The function allocates memory for each valid formatted IP address and returns an array of pointers to these strings.
  3. Iterate over the resulting array to access each generated IP address.
  4. Free the allocated memory when no longer needed to avoid memory leaks.

Ensure correct handling of memory allocation and boundary conditions when using these functions.

js 
var isSegmentValid = function (str, idx, len) {
    return (
        len === 1 ||
        (str[idx] !== "0" && (len < 3 || str.substr(idx, len) <= "255"))
    );
};
var generateIpAddresses = function (inputStr) {
    let result = [];
    let strLength = inputStr.length;
    for (
        let firstLen = Math.max(1, strLength - 9);
        firstLen <= 3 && firstLen <= strLength - 3;
        ++firstLen
    ) {
        if (!isSegmentValid(inputStr, 0, firstLen)) continue;
        for (
            let secondLen = Math.max(1, strLength - firstLen - 6);
            secondLen <= 3 && secondLen <= strLength - firstLen - 2;
            ++secondLen
        ) {
            if (!isSegmentValid(inputStr, firstLen, secondLen)) continue;
            for (
                let thirdLen = Math.max(1, strLength - firstLen - secondLen - 3);
                thirdLen <= 3 && thirdLen <= strLength - firstLen - secondLen - 1;
                ++thirdLen
            ) {
                if (
                    isSegmentValid(inputStr, firstLen + secondLen, thirdLen) &&
                    isSegmentValid(inputStr, firstLen + secondLen + thirdLen, strLength - firstLen - secondLen - thirdLen)
                ) {
                    result.push(
                        inputStr.substr(0, firstLen) +
                            "." +
                            inputStr.substr(firstLen, secondLen) +
                            "." +
                            inputStr.substr(firstLen + secondLen, thirdLen) +
                            "." +
                            inputStr.substr(firstLen + secondLen + thirdLen)
                    );
                }
            }
        }
    }
    return result;
};

The JavaScript code provided outlines an efficient approach to solving the problem of restoring valid IP addresses from a given string. This function is essential for applications such as form validations or network configurations where input integrity is of high importance.

Exploration of Code Mechanics

  • The isSegmentValid function determines if a particular segment of the string can be a valid part of an IP address. It returns true if:

    • The segment is of length 1, or
    • It does not start with '0' unless it is '0' itself, and it forms a number less than or equal to 255 if it has 3 digits.

  • generateIpAddresses initializes an empty array result to store the valid IP addresses and uses nested loops to generate all possible IP addresses:

    • It decides the lengths of the first, second, and third segments of the potential IP address progressively.
    • Each loop checks if the current length makes a valid segment of an IP address using the isSegmentValid function.

Handling IP Fragmentation

The segment lengths are dynamically determined based on the remaining string length, ensuring that each segment is no longer than 3 characters and allowing for the remaining parts of the IP address to be formed correctly.

Assembling the Address

If all four computed segments are valid, the segments are concatenated with dots to form an IP address which is then added to the result list.

Output and Usage

After processing, generateIpAddresses returns an array of string, where each string is a valid IP address format derived from the input string. This utility function proves instrumental in scenarios where you need to parse strings to extract potential IP addresses without explicit segmentation marks.

python 
class IPAddressRestorer:
    def findValidIPs(self, str):
        def check_segment(segment_start, seg_len):
            if segment_start >= len(str):
                return False
            if seg_len == 1 or (str[segment_start] != "0" and (seg_len < 3 or int(str[segment_start : segment_start + seg_len]) <= 255)):
                return True
            return False

        output = []
        str_length = len(str)
        for first_seg_len in range(max(1, str_length - 9), min(4, str_length - 2) + 1):
            if not check_segment(0, first_seg_len):
                continue
            for second_seg_len in range(max(1, str_length - first_seg_len - 6), min(4, str_length - first_seg_len - 1) + 1):
                if not check_segment(first_seg_len, second_seg_len):
                    continue
                for third_seg_len in range(max(1, str_length - first_seg_len - second_seg_len - 3), min(4, str_length - first_seg_len - second_seg_len) + 1):
                    if check_segment(first_seg_len + second_seg_len, third_seg_len) and check_segment(first_seg_len + second_seg_len + third_seg_len, str_length - first_seg_len - second_seg_len - third_seg_len):
                        output.append(str[:first_seg_len] + "." + str[first_seg_len:first_seg_len + second_seg_len] + "." + str[first_seg_len + second_seg_len:first_seg_len + second_seg_len + third_seg_len] + "." + str[first_seg_len + second_seg_len + third_seg_len:])
        return output

The Python solution provided outlines an approach to restore IP addresses from a given string of digits by defining a class IPAddressRestorer with a method findValidIPs. The method attempts to construct valid IP addresses by segmenting the string into four parts where each segment must meet specific criteria:

  • Dissects the input string into four segments using nested loops to explore different segment lengths.
  • Segments are validated by:
    • Ensuring they start with a non-zero, unless the segment is exactly '0'.
    • Checking that segments do not exceed the maximum allowed value of 255 for IP address segments.

The process involves:

  • Iterating over possible lengths for the first segment, followed sequentially by possible lengths for the second and third segments based on remaining characters.
  • Validating each segment with a helper function check_segment that:
    • Confirms the segment is within the bounds.
    • Determines if it meets the numerical criteria.
  • Constructs potential IP addresses when valid segments are identified.

This structured and trial-based approach gradually compiles a list of valid IP configurations which are returned after all possible combinations are examined. This method ensures you only get valid and correctly formatted IP addresses according to the rules of IP formatting, helping in scenarios where raw input strings need conversion to structured IP addresses.

Comments

No comments yet.