Jobs

Interviews

Discussions

Restore IP Addresses

Medium

Asked by:

+12

28 views

Topics:

StringsRecursion

A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.

For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.

Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You are not allowed to reorder or remove any digits in s. You may return the valid IP addresses in any order.

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.

Restore IP Addresses

Medium

Asked by:

28 views

Topics:

StringsRecursion

A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.

For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.

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.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string `s`? Is there a minimum length?
If the input string `s` cannot be split into four valid integers between 0 and 255, should I return an empty list or null?
Can the input string `s` contain leading zeros? If so, how should I handle them when forming the IP address (e.g., is "01" valid)?
Are there any constraints on the order in which the valid IP addresses should be returned?
Is the input string guaranteed to contain only digits, or could it contain other characters?

Brute Force Solution

Approach

The problem asks us to find all possible valid IP addresses that can be formed from a given string of digits. A brute force approach is like trying every single way to divide the string into four parts and then checking if each part is a valid number between 0 and 255.

Here's how the algorithm would work step-by-step:

Consider all the possible ways to split the digit string into four parts.
For each possible split, check if each of the four parts is a valid number to be part of an IP address.
A valid IP address part must be a number between 0 and 255.
If a part starts with a zero, it can only be a single zero itself, otherwise, it is invalid.
If all four parts of a split are valid numbers, then we have found a valid IP address.
Repeat for every single possible way to split the digit string.
Collect all the valid IP addresses we found and return them.

Code Implementation

def restore_ip_addresses(digits):
    possible_ip_addresses = []
    string_length = len(digits)

    # Iterate through all possible first segment lengths
    for first_segment_length in range(1, min(4, string_length)):
        # Iterate through all possible second segment lengths
        for second_segment_length in range(1, min(4, string_length - first_segment_length)):
            # Iterate through all possible third segment lengths
            for third_segment_length in range(1, min(4, string_length - first_segment_length - second_segment_length)):
                fourth_segment_length = string_length - first_segment_length - second_segment_length - third_segment_length

                # Ensure the fourth segment has a valid length
                if 1 <= fourth_segment_length <= 3:
                    first_segment = digits[0:first_segment_length]
                    second_segment = digits[first_segment_length:first_segment_length + second_segment_length]
                    third_segment = digits[first_segment_length + second_segment_length:first_segment_length + second_segment_length + third_segment_length]
                    fourth_segment = digits[first_segment_length + second_segment_length + third_segment_length:]

                    # Validate each segment
                    if is_valid_segment(first_segment) and \
                       is_valid_segment(second_segment) and \
                       is_valid_segment(third_segment) and \
                       is_valid_segment(fourth_segment):

                        # Join the valid segments to form the IP address
                        ip_address = first_segment + "." + second_segment + "." + third_segment + "." + fourth_segment
                        possible_ip_addresses.append(ip_address)

    return possible_ip_addresses

def is_valid_segment(segment):
    # Segments starting with zero must be exactly zero.
    if segment.startswith('0') and segment != '0':
        return False

    # Ensure segments are between 0 and 255.
    if int(segment) > 255:
        return False

    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(1) – The length of the input string 's' is bounded by a small constant (typically, a maximum of 12 digits, since each of the four parts of an IP address can have at most 3 digits). The algorithm iterates through all possible splits of the string into four parts, checking the validity of each part. Since the maximum length of the string is limited, the number of possible splits is also limited by a constant. Consequently, the time complexity does not grow with the input size and is therefore O(1).

Space Complexity

O(1) – The space complexity is dominated by the auxiliary space used to store the current valid IP address being built, as well as a small amount of space to hold the four parts of the potential IP address. The depth of the recursion is fixed to four levels (representing the four parts of an IP address). Because the amount of storage used is not dependent on the input digit string's length (N), the space required is constant. The space used for storing the IP address parts and the current IP address does not scale with the input size. Thus, the space complexity can be considered O(1).

Optimal Solution

Approach

The goal is to find all the valid ways to split a string into four parts, where each part represents a number between 0 and 255. Instead of checking every possible split, the approach breaks down the problem into smaller parts and builds valid IP addresses piece by piece.

Here's how the algorithm would work step-by-step:

Think of the string as a sequence of digits. We need to insert three separators to create four numbers.
Start by choosing the position of the first separator. The first number must be between 0 and 255, so only certain starting sections are valid.
Once the first number is chosen, consider possible positions for the second separator, keeping in mind that the second number must also be between 0 and 255.
Continue this process for the third separator, ensuring the third number is valid.
Finally, check if the remaining digits form a valid fourth number (between 0 and 255).
If all four numbers are valid, we've found a valid IP address. Save it.
Repeat this process by trying different positions for the separators until we've explored all valid combinations. The key is to only proceed if the numbers created so far are valid.
Return the collection of valid IP addresses found.

Code Implementation

def restore_ip_addresses(ip_string):
    possible_ip_addresses = []

    def is_valid_part(ip_part):
        if not ip_part:
            return False
        if len(ip_part) > 1 and ip_part[0] == '0':
            return False
        if int(ip_part) > 255:
            return False
        return True

    def backtrack(index, parts, current_ip):
        # If we have four parts and have used all characters.
        if len(parts) == 4:
            if index == len(ip_string):
                possible_ip_addresses.append(current_ip[:-1])
            return

        # Limiting the search space by validating only reasonable parts.
        for i in range(index + 1, min(index + 4, len(ip_string) + 1)):
            ip_part = ip_string[index:i]
            
            if is_valid_part(ip_part):
                # Add current part, and backtrack.
                backtrack(i, parts + [ip_part], current_ip + ip_part + '.')

    # Begin backtracking with initial conditions
    backtrack(0, [], '')
    return possible_ip_addresses

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(1) – The length of the input string 's' is constrained to a maximum of 12 digits because each of the four segments of the IP address can have at most three digits to be within the range 0-255. The algorithm explores all possible placements of three separators within this string. Since the maximum length of the string is fixed, the number of possible separator placements is also bounded by a constant. Therefore, the time complexity does not grow with an arbitrarily large input size, and the runtime is effectively constant.

Space Complexity

O(1) – The algorithm uses a constant amount of auxiliary space. It stores a few variables such as the positions of separators. The space required for these variables does not depend on the length N of the input string. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Empty input string	Return an empty list immediately as an empty string cannot form a valid IP address.
Input string length less than 4	Return an empty list because a valid IP address needs at least 4 digits.
Input string length greater than 12	Return an empty list as a valid IP address can have at most 12 digits (4 numbers each up to 3 digits).
Input string containing non-digit characters	Throw an exception or return an empty list as the problem specifies the input string contains only digits; validating this ensures code robustness.
Leading zero in a segment, except for a single zero	Reject any segment with a leading zero if its length is greater than 1.
Segment value greater than 255	Reject any segment whose integer value is greater than 255.
No valid IP address possible	The recursive/backtracking algorithm will naturally handle this by not adding any invalid results to the list of valid IP addresses, eventually returning an empty list.
Integer overflow when converting a string segment to an integer	Use appropriate data types (e.g., `int`) and boundary checks to prevent integer overflow during conversion.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string `s`? Is there a minimum length?
If the input string `s` cannot be split into four valid integers between 0 and 255, should I return an empty list or null?
Can the input string `s` contain leading zeros? If so, how should I handle them when forming the IP address (e.g., is "01" valid)?
Are there any constraints on the order in which the valid IP addresses should be returned?
Is the input string guaranteed to contain only digits, or could it contain other characters?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider all the possible ways to split the digit string into four parts.
For each possible split, check if each of the four parts is a valid number to be part of an IP address.
A valid IP address part must be a number between 0 and 255.
If a part starts with a zero, it can only be a single zero itself, otherwise, it is invalid.
If all four parts of a split are valid numbers, then we have found a valid IP address.
Repeat for every single possible way to split the digit string.
Collect all the valid IP addresses we found and return them.

Code Implementation

def restore_ip_addresses(digits):
    possible_ip_addresses = []
    string_length = len(digits)

    # Iterate through all possible first segment lengths
    for first_segment_length in range(1, min(4, string_length)):
        # Iterate through all possible second segment lengths
        for second_segment_length in range(1, min(4, string_length - first_segment_length)):
            # Iterate through all possible third segment lengths
            for third_segment_length in range(1, min(4, string_length - first_segment_length - second_segment_length)):
                fourth_segment_length = string_length - first_segment_length - second_segment_length - third_segment_length

                # Ensure the fourth segment has a valid length
                if 1 <= fourth_segment_length <= 3:
                    first_segment = digits[0:first_segment_length]
                    second_segment = digits[first_segment_length:first_segment_length + second_segment_length]
                    third_segment = digits[first_segment_length + second_segment_length:first_segment_length + second_segment_length + third_segment_length]
                    fourth_segment = digits[first_segment_length + second_segment_length + third_segment_length:]

                    # Validate each segment
                    if is_valid_segment(first_segment) and \
                       is_valid_segment(second_segment) and \
                       is_valid_segment(third_segment) and \
                       is_valid_segment(fourth_segment):

                        # Join the valid segments to form the IP address
                        ip_address = first_segment + "." + second_segment + "." + third_segment + "." + fourth_segment
                        possible_ip_addresses.append(ip_address)

    return possible_ip_addresses

def is_valid_segment(segment):
    # Segments starting with zero must be exactly zero.
    if segment.startswith('0') and segment != '0':
        return False

    # Ensure segments are between 0 and 255.
    if int(segment) > 255:
        return False

    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Think of the string as a sequence of digits. We need to insert three separators to create four numbers.
Start by choosing the position of the first separator. The first number must be between 0 and 255, so only certain starting sections are valid.
Once the first number is chosen, consider possible positions for the second separator, keeping in mind that the second number must also be between 0 and 255.
Continue this process for the third separator, ensuring the third number is valid.
Finally, check if the remaining digits form a valid fourth number (between 0 and 255).
If all four numbers are valid, we've found a valid IP address. Save it.
Repeat this process by trying different positions for the separators until we've explored all valid combinations. The key is to only proceed if the numbers created so far are valid.
Return the collection of valid IP addresses found.

Code Implementation

def restore_ip_addresses(ip_string):
    possible_ip_addresses = []

    def is_valid_part(ip_part):
        if not ip_part:
            return False
        if len(ip_part) > 1 and ip_part[0] == '0':
            return False
        if int(ip_part) > 255:
            return False
        return True

    def backtrack(index, parts, current_ip):
        # If we have four parts and have used all characters.
        if len(parts) == 4:
            if index == len(ip_string):
                possible_ip_addresses.append(current_ip[:-1])
            return

        # Limiting the search space by validating only reasonable parts.
        for i in range(index + 1, min(index + 4, len(ip_string) + 1)):
            ip_part = ip_string[index:i]
            
            if is_valid_part(ip_part):
                # Add current part, and backtrack.
                backtrack(i, parts + [ip_part], current_ip + ip_part + '.')

    # Begin backtracking with initial conditions
    backtrack(0, [], '')
    return possible_ip_addresses

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input string	Return an empty list immediately as an empty string cannot form a valid IP address.
Input string length less than 4	Return an empty list because a valid IP address needs at least 4 digits.
Input string length greater than 12	Return an empty list as a valid IP address can have at most 12 digits (4 numbers each up to 3 digits).
Input string containing non-digit characters	Throw an exception or return an empty list as the problem specifies the input string contains only digits; validating this ensures code robustness.
Leading zero in a segment, except for a single zero	Reject any segment with a leading zero if its length is greater than 1.
Segment value greater than 255	Reject any segment whose integer value is greater than 255.
No valid IP address possible	The recursive/backtracking algorithm will naturally handle this by not adding any invalid results to the list of valid IP addresses, eventually returning an empty list.
Integer overflow when converting a string segment to an integer	Use appropriate data types (e.g., `int`) and boundary checks to prevent integer overflow during conversion.