Every Valid IPv4 Address Restorable From a Digit String
Solve this ProblemTest Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ digits.length ≤ 12 - ◆
digits consists only of digits '0'–'9' - ◆
A valid IPv4 part is 0–255 with no leading zero, unless the part is exactly "0" - ◆
Results are returned sorted in ascending (lexicographic) order for a stable, checkable answer
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Every Length Combination, Validate All Four Parts
BruteEach of the 4 parts can independently be 1, 2, or 3 digits long, so four nested loops try all 3⁴ = 81 length combinations without any awareness of whether they add up to the actual input length. Only after picking a full (len1, len2, len3, len4) combination does the code check whether those lengths even sum to the total digit count — and only then does it slice out and validate all four parts. Since the total length is fixed by the constraints, this really is O(1) work overall, but nearly all of that fixed work (most of the 81 combinations) is thrown away on a length mismatch discovered only after the fact.
O(1)O(1)1class Solution {
2 public String[] restorableIpAddresses(String digits) {
3 int n = digits.length();
4 List<String> result = new ArrayList<>();
5 for (int len1 = 1; len1 <= 3; len1++) {
6 for (int len2 = 1; len2 <= 3; len2++) {
7 for (int len3 = 1; len3 <= 3; len3++) {
8 for (int len4 = 1; len4 <= 3; len4++) {
9 if (len1 + len2 + len3 + len4 != n) continue;
10 int i1 = len1, i2 = len1 + len2, i3 = len1 + len2 + len3;
11 String p1 = digits.substring(0, i1);
12 String p2 = digits.substring(i1, i2);
13 String p3 = digits.substring(i2, i3);
14 String p4 = digits.substring(i3, n);
15 if (isValidPart(p1) && isValidPart(p2) && isValidPart(p3) && isValidPart(p4)) {
16 result.add(p1 + "." + p2 + "." + p3 + "." + p4);
17 }
18 }
19 }
20 }
21 }
22 Collections.sort(result);
23 return result.toArray(new String[0]);
24 }
25
26 private boolean isValidPart(String p) {
27 if (p.length() > 1 && p.charAt(0) == '0') return false;
28 int value = Integer.parseInt(p);
29 return value <= 255;
30 }
31}Optimal — Track Remaining Budget, Prune Before Slicing
OptimalBuild the four parts one at a time. Before even slicing out a candidate piece, compute how many digits would be left over and compare that to how many parts still need to be filled — if there aren't enough digits left for the remaining parts (or there are too many, more than 3 per remaining part), that length is skipped immediately, with no substring ever created and no validity check ever run. Only a length that could plausibly fit gets sliced out and checked. Both approaches do a bounded, constant amount of work given the fixed input size, but this version's constant factor is far smaller — the fewer valid paths there are, the less of the search space it ever has to touch.
O(1)O(1)1class Solution {
2 public String[] restorableIpAddresses(String digits) {
3 List<String> result = new ArrayList<>();
4 List<String> parts = new ArrayList<>();
5 backtrack(digits, 0, parts, result);
6 return result.toArray(new String[0]);
7 }
8
9 private void backtrack(String digits, int start, List<String> parts, List<String> result) {
10 if (parts.size() == 4) {
11 if (start == digits.length()) {
12 result.add(String.join(".", parts));
13 }
14 return;
15 }
16 int remainingParts = 4 - parts.size() - 1;
17 for (int len = 1; len <= 3 && start + len <= digits.length(); len++) {
18 int remainingDigits = digits.length() - (start + len);
19 if (remainingDigits < remainingParts || remainingDigits > remainingParts * 3) continue;
20 String piece = digits.substring(start, start + len);
21 if (isValidPart(piece)) {
22 parts.add(piece);
23 backtrack(digits, start + len, parts, result);
24 parts.remove(parts.size() - 1);
25 }
26 }
27 }
28
29 private boolean isValidPart(String p) {
30 if (p.length() > 1 && p.charAt(0) == '0') return false;
31 int value = Integer.parseInt(p);
32 return value <= 255;
33 }
34}