Sponsored
Sponsored
This approach utilizes backtracking to explore all possible placements of the three dots in the string. We attempt to generate valid IP segments recursively, ensuring each generated segment maintains the restrictions of a valid IP address. By backtracking, we can explore each possible path of placing dots and ensure we cover all potential valid configurations.
Time Complexity: O(2^n), due to the exponential number of ways to split the string, though practical time for small strings like ours is quite feasible.
Space Complexity: O(n), for the recursion stack and to store the IP parts temporarily.
1def restore_ip_addresses(s):
2 def backtrack(start, parts):
3 if len(parts) == 4:
4 if start == len(s):
5 result.append(".".join(parts))
6 return
7
8 for i in range(1, 4):
9 if start + i > len(s):
10 break
11 part = s[start:start+i]
12 if (len(part) > 1 and part[0] == '0') or (int(part) > 255):
13 continue
14 backtrack(start + i, parts + [part])
15
16 result = []
17 backtrack(0, [])
18 return result
19
20# Example usage:
21# restore_ip_addresses("25525511135")This Python function defines a helper function backtrack, which takes the current starting index and a list of constructed IP parts. We recursively attempt to build valid segments, ensuring they adhere to IP rules (no leading zeros, within [0, 255] range), and append valid results to the result list. We explore segments of lengths 1 to 3, backtracking appropriately.
In this approach, we iterate through potential splits for the three dots required to form four IP sections. For each potential set of positions, we validate and construct the IP address. Although typically not as elegant as the recursive backtracking solution, it's systematic and allows us to explore and validate possible IP addresses through combinatorial checks.
Time Complexity: O(n^3), given the triple nested loop for positions.
Space Complexity: O(1), ignoring the output list space.
1function restoreIpAddresses(s) {
2 const
This JavaScript function constructs IP addresses using triple nested loops similar to the C++ solution. It calculates the potential dot positions, generates candidate segments, and verifies their validity using a custom isValid function before adding them to the result array if they form a valid IP address.