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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Restore IP Addresses

Number: 93

Difficulty: Medium

Paid? No

Companies: Microsoft, Arista Networks, Nvidia, Visa, Amazon, TikTok, Google, Meta, Zoho, Goldman Sachs, Yandex, Adobe, Oracle

Problem Description

Given a string containing only digits, restore all possible valid IP addresses by inserting exactly three dots into the string. A valid IP address consists of four integers, each between 0 and 255 inclusive, and no integer (except 0) can have leading zeros.

Key Insights

  • Use a backtracking approach to explore different segmentations of the input string.
  • IP addresses contain exactly four segments; once four segments are generated, the entire string must have been used.
  • Validate each segment to ensure it is within the range [0, 255] and does not have leading zeros (unless the segment is "0").
  • Prune the search if the remaining characters do not allow forming a valid IP address (too short or too long).

Space and Time Complexity

Time Complexity: O(N^4) in the worst-case scenario where N is the length of the string, though N is bounded by string length constraints. Space Complexity: O(N) for the recursion call stack and temporary storage, where N is the length of the string.

Solution

We use a backtracking recursive approach to partition the string into four segments. At each recursive call, we try all possible segment lengths (1 to 3 characters) while ensuring that:

  1. The chosen segment does not exceed the string's bounds.
  2. The segment does not have any invalid leading zeros (unless the segment is "0").
  3. The numeric value of the segment lies between 0 and 255.

Once four segments are collected, we check if all characters in the string have been consumed. If so, we join the segments with dots and add the resulting IP address to the final answer list.

Code Solutions

# Python solution using backtracking

class Solution:
    def restoreIpAddresses(self, s: str) -> list:
        result = []  # List to store valid IP addresses
        
        def backtrack(start: int, path: list):
            # If 4 parts are collected and we've used all characters, record the result
            if len(path) == 4 and start == len(s):
                result.append(".".join(path))
                return
            # If either 4 parts are collected or not enough parts remain, prune the search
            if len(path) == 4 or start == len(s):
                return
            
            # Try each segment length from 1 to 3
            for length in range(1, 4):
                # Avoid index overflow
                if start + length > len(s):
                    break
                segment = s[start:start+length]
                # Check for leading zeros (segment "0" is valid)
                if len(segment) > 1 and segment[0] == '0':
                    continue
                # Convert segment to integer and check valid range [0, 255]
                if int(segment) > 255:
                    continue
                # Append segment to path and backtrack for next segment
                backtrack(start + length, path + [segment])
        
        backtrack(0, [])
        return result

# Example usage:
# sol = Solution()
# print(sol.restoreIpAddresses("25525511135"))
← Back to All Questions