93. Restore IP Addresses
Someone stripped every dot out of an IPv4 address, leaving only the digit string s. Your job is to put the dots back: find every way to insert exactly three dots into s so that the result is a valid IPv4 address.
An address is valid when it has four parts, each part is a number from 0 to 255, and no part has a leading zero — "0" is fine, but "01" and "00" are not. Every digit of s must be used, in the original order, and you may not add, drop, or reorder digits.
Given s, return all valid addresses sorted in lexicographic (dictionary) order as strings. If no valid address can be formed, return an empty list.
Example 1:
Input: s = "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]
Explanation: Two dot placements survive the 0–255 and leading-zero rules. "255.255.11.135" sorts first because '.' comes before '1'.
Example 2:
Input: s = "101023"
Output: ["1.0.10.23", "1.0.102.3", "10.1.0.23", "10.10.2.3", "101.0.2.3"]
Explanation: Five splits are valid; note that "10.10.23" style groupings with a stray "02" part are rejected for the leading zero.
Example 3:
Input: s = "0000"
Output: ["0.0.0.0"]
Explanation: Each part is exactly "0", which is the only legal way to write zero.
Constraints:
- 1 ≤ s.length ≤ 20
- s contains only digits 0-9
Hints:
Quick sanity bounds first: four parts of 1–3 digits means only strings of length 4 to 12 can produce anything at all.
A part is valid when it is 1–3 digits, its number is at most 255, and it does not start with '0' unless it is exactly "0". Write that check once and reuse it everywhere.
There are only three dots to place — either enumerate all cut positions directly, or backtrack segment by segment, pruning when the remaining digits cannot fill the remaining parts (fewer than 1 or more than 3 per part).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "25525511135"
Expected output: ["255.255.11.135", "255.255.111.35"]