How do you solve Restore IP Addresses on LeetCode?

Restore IP Addresses (LeetCode #93) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Valid segments must be between 0 and 255.

What is the brute force solution for Restore IP Addresses?

The brute force approach for Restore IP Addresses is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach generates all possible combinations of inserting dots in the string and then checks each combination to see if it's a valid IP address. This method is straightforward but inefficient as it explores many unnecessary combinations. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Restore IP Addresses?

Restore IP Addresses uses the following concepts: String, Backtracking. The recommended patterns to study are: Backtracking, Recursion.

What are the interview tips for Restore IP Addresses?

Think about edge cases, like minimum and maximum lengths of the input string. Explain your thought process clearly while coding. Practice backtracking problems to get comfortable with recursive solutions.

What are common mistakes when solving Restore IP Addresses?

Not checking for leading zeros in segments. Failing to handle cases where the string length is less than 4.

#93

Restore IP Addresses

Medium

StringBacktrackingBacktrackingRecursion

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses backtracking to explore valid segments of the IP address. This approach is efficient because it avoids generating invalid segments early, reducing unnecessary checks.

⚙️

Algorithm

3 steps

1Step 1: Use a backtracking function to build segments of the IP address.
2Step 2: If four segments are formed and the string is fully used, add the IP to the results.
3Step 3: If the segment is valid, recursively call the function for the next segment.

solution.py15 lines

1def restore_ip_addresses(s):
2    def backtrack(start, path):
3        if len(path) == 4 and start == len(s):
4            result.append('.'.join(path))
5            return
6        for length in range(1, 4):
7            if start + length <= len(s):
8                segment = s[start:start + length]
9                if is_valid(segment):
10                    backtrack(start + length, path + [segment])
11    def is_valid(segment):
12        return 0 <= int(segment) <= 255 and str(int(segment)) == segment
13    result = []
14    backtrack(0, [])
15    return result

ℹ

Complexity note: The time complexity is O(n) because we only traverse the string once while generating segments. The space complexity is O(n) due to the storage of valid IP addresses in the result list.

1Valid segments must be between 0 and 255.
2Segments cannot have leading zeros unless they are '0'.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.