algoadvance

The problem “93. Restore IP Addresses” requires you to restore all possible valid IP address combinations from a given string consisting of only digits. An IP address consists of four decimal numbers, each ranging from 0 to 255, separated by dots (.). The input string should be partitioned into these four parts to build valid IP addresses. Return these IP addresses in any order.

The constraints are:

  1. The input string may only contain digits.
  2. The length of the string is between 1 and 20.

Clarifying Questions

  1. Is it necessary to validate the leading zeros?
    • Yes, an octet cannot have leading zeros unless it is exactly ‘0’.
  2. Should the IP addresses be returned in any particular order?
    • No, the IP addresses can be returned in any order.
  3. What should be done if the string length is not between the typical range for an IP address (4 to 12 digits)?
    • If the string’s length is outside this range, the function should return an empty list.

Strategy

We will use a backtracking approach to generate all valid combinations of IP addresses. Here’s the general strategy:

  1. Start with an empty path and initiate a recursive function to explore segments of the string.
  2. Keep track of the current segment being formed.
  3. If a segment leads to an invalid IP address part (e.g., starting with 0 but has more than one digit), skip that combination.
  4. If a valid combination of four segments is found, join them with dots and add to the result list.
  5. Continue the process until all combinations are explored.

Code

Here’s the Python implementation of the strategy:

def restoreIpAddresses(s):
    def is_valid(segment):
        # Check if the segment is valid:
        # 1. Length should be between 1 and 3
        # 2. No leading zero unless it is '0'
        # 3. Should be less than or equal to 255
        return len(segment) == 1 or (segment[0] != '0' and int(segment) <= 255)

    def backtrack(start=0, path=[]):
        # If we have 4 segments and we have reached the end of the string,
        # we found a valid IP address
        if len(path) == 4:
            if start == len(s):
                result.append(".".join(path))
            return
        
        # Try to place "." after each 1 to 3 characters
        for end in range(start + 1, min(start + 4, len(s) + 1)):
            segment = s[start:end]
            if is_valid(segment):
                backtrack(end, path + [segment])

    result = []
    backtrack()
    return result

# Example Usage
s = "25525511135"
print(restoreIpAddresses(s))

Time Complexity

The time complexity of this solution is O(3^4), which simplifies to O(81) or O(1) as this is constant time for valid IP address partitions. Here’s why:

While there is some additional complexity related to the string slicing and validations, the crucial point is the number of recursive calls, which is fixed and manageable.

This backtracking approach ensures efficient and correct generation of all possible valid IP addresses from the provided string.

Try our interview co-pilot at AlgoAdvance.com