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.
1import java.util.*;
2
3public class RestoreIPAddresses {
4 public List<String> restoreIpAddresses(String s) {
5 List<String> result = new ArrayList<>();
6 backtrack(result, new ArrayList<>(), s, 0);
7 return result;
8 }
9
10 private void backtrack(List<String> result, List<String> temp, String s, int start) {
11 if (temp.size() == 4) {
12 if (start == s.length()) {
13 result.add(String.join(".", temp));
14 }
15 return;
16 }
17
18 for (int len = 1; len <= 3; len++) {
19 if (start + len > s.length()) break;
20 String part = s.substring(start, start + len);
21 if ((part.startsWith("0") && part.length() > 1) || Integer.parseInt(part) > 255) continue;
22 temp.add(part);
23 backtrack(result, temp, s, start + len);
24 temp.remove(temp.size() - 1);
25 }
26 }
27
28 public static void main(String[] args) {
29 RestoreIPAddresses rip = new RestoreIPAddresses();
30 System.out.println(rip.restoreIpAddresses("25525511135"));
31 }
32}This Java solution employs backtracking similar to the above Python solution. We use a helper backtrack method that adds potential IP segments (temp) to the result list, if valid. We try segments of length 1 to 3 unless they lead to invalid segments (starting with zero, etc.). Once a complete 4-segment IP is built, it is added to result if it consumes all input characters.
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.