We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Restore IP Addresses

Difficulty: Medium

Problem Description

Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. 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.

Key Insights

  • An IP address consists of four segments, each representing a number between 0 and 255.
  • Each segment can have a maximum of three digits.
  • Segments cannot have leading zeros unless the segment is "0" itself.
  • Use backtracking to explore all possible ways to insert three dots into the string.

Space and Time Complexity

Time Complexity: O(1) - The maximum number of valid IP addresses is limited by the constraints, so we can consider this constant time for practical purposes. Space Complexity: O(n) - Space used for storing valid IP addresses, where n is the number of valid addresses generated.

Solution

The problem can be solved using a backtracking approach. We will recursively try to form segments of the IP address by taking 1 to 3 digits at a time. Each time we take a segment, we check if it is valid (i.e., between 0 and 255 and does not have leading zeros). If we have formed 4 segments and used all digits in the string, we add the current combination to our list of valid IP addresses.

The data structures used include:

  • A list to store valid IP addresses.
  • A temporary string to build the current IP address.

Code Solutions

def restore_ip_addresses(s):
    def backtrack(start=0, path=[]):
        if len(path) == 4:
            if start == len(s):
                result.append('.'.join(path))
            return
        
        for length in range(1, 4):  # Segment length can be 1 to 3
            if start + length > len(s):  # Out of bounds
                break
            segment = s[start:start + length]
            if (len(segment) > 1 and segment[0] == '0') or int(segment) > 255:
                continue
            path.append(segment)
            backtrack(start + length, path)
            path.pop()  # Backtrack

    result = []
    backtrack()
    return result

# Example usage:
print(restore_ip_addresses("25525511135"))  # Output: ["255.255.11.135", "255.255.111.35"]
← Back to All Questions