Recover Dotted Addresses
MediumBacktracking
Problem
A log file lost the dots in its IPv4 addresses, leaving only a string of digits s. An IPv4 address is four parts separated by dots; each part is an integer from 0 to 255 written without leading zeros (0 is fine, 01 is not).
Return every valid address that could have produced s by deleting its three dots, in any order.
Example 1
- Input:
- s = "25525511135"
- Output:
- ["255.255.11.135", "255.255.111.35"]
"255.255.1.1135" is invalid because 1135 > 255.
Example 2
- Input:
- s = "0000"
- Output:
- ["0.0.0.0"]
Constraints
- 1 ≤ s.length ≤ 20
- s contains only digits.
Hint
Show the first hint
Each part takes 1, 2 or 3 characters. That is at most 3^4 = 81 ways to cut the string.
Walkthrough
How to approach it
01Clarify before coding
- Are leading zeros allowed? Only the single digit '0'; '00' and '01' are invalid.
- Must all digits be used? Yes, deleting only the dots.
- What if the length is below 4 or above 12? No address is possible: return [].
02Brute force
Try every placement of three dots among the n - 1 gaps, then validate the four parts.
Cost: O(n^3) placements; fine for the stated sizes, but it does not stop early on a bad first part and is clumsy to extend.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.