Restore IP Addresses
mediumTime: O(1)Space: O(1)
Signals to notice
split string into 4 valid IP segments1-3 digits per segment0-255 no leading zeros
Brute force first
Try all 3 split points — O(n³).
The key insight
Backtracking: take 1-3 digits, validate (0-255, no leading zeros), recurse. 4 segments must consume all characters. O(1) since input ≤ 12 chars.
What must stay true
Each segment: 1-3 digits, value 0-255, no leading zeros (except '0' alone). Exactly 4 segments consuming the full string.
Easy way to go wrong
Allowing '01' — only '0' is valid as a leading-zero segment.