Restore IP Addresses medium
Description
A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros (so "0" is valid, "01" is not).
Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You may not reorder or remove any digits.
Examples
> Case 1:
s = "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]
> Case 2:
s = "0000"
Output: ["0.0.0.0"]
> Case 3:
s = "101023"
Output: ["1.0.10.23", "1.0.102.3", "10.1.0.23", "10.10.2.3", "101.0.2.3"]Constraints
1 <= s.length <= 20sconsists of digits only.
State design
A fixed-piece partition — exactly 4 pieces. So unlike Palindrome Partitioning where we recurse until the string runs out, here we recurse with an additional count of pieces used so far.
- Partial solution?
path— the IP octets so far. Plus astartindex andpiecescount. - Complete? When
start == len(s)ANDpieces == 4. - Choices?
endin[start + 1, start + 3](each octet is 1-3 chars). - Legality? The substring is a valid octet (≤ 255, no leading zero unless it’s literally
"0"), AND total chars left can fill remaining pieces. - Undo? Pop the piece after recursing.
The “total chars left can fill remaining pieces” check is the pruning win.
Code
The length-bound prune is killer. With slots = 4 - pieces remaining slots, the leftover digits must satisfy slots <= remaining <= 3 * slots. Outside that band, no completion can possibly work. One O(1) check trims huge subtrees.
Analysis
- Time:
O(1)— the input is bounded bys.length() <= 20, so the answer set is bounded by a constant. Treatingnas variable:O(3^4) = O(81)candidate placements per starting position, but pruning brings it well below that in practice. - Space:
O(1)recursion (depth ≤ 4).
Same skin
- Partition Into 4 Equal-Sum Subsets — exact-piece partition, harder validation.
- Palindrome Partitioning II — fixed-piece minimum (each piece a palindrome).
- Decode Ways — partition a digit string into pieces of length 1 or 2, each valid (1-26).
- Word Break II — partition into dictionary words; not fixed count.