Restore IP Addresses
mediumTime: O(1)Space: O(1)
Recognize the pattern
split string into 4 valid IP segments1-3 digits per segment0-255 no leading zeros
Brute force idea
Try all 3 split points — O(n³).
Better approach
Backtracking: take 1-3 digits, validate (0-255, no leading zeros), recurse. 4 segments must consume all characters. O(1) since input ≤ 12 chars.
Key invariant
Each segment: 1-3 digits, value 0-255, no leading zeros (except '0' alone). Exactly 4 segments consuming the full string.
Watch out for
Allowing '01' — only '0' is valid as a leading-zero segment.