Restore the address
List every way to put dots into a string of digits so it becomes a valid IP address of four numbers from 0 to 255, with no number starting with a zero unless it is zero itself. About 20 minutes.
Four parts, one to three digits
An address has exactly four parts. Each part is a number from 0 to 255, written without a leading zero, so 0 is fine but 01 is not. That means each part has one, two or three digits.
Choose the parts from left to right. For each part, try the sizes 1, 2 and 3, and keep only those that make a valid number.
piece = s[i:i + 3] ok = int(piece) <= 255 and piece[0] != "0"
The first part 10 is valid (2 digits).
Use every digit
A route is complete when four parts have been chosen and the digits are used up exactly. If the parts are done but digits remain, it is not a solution. If the digits run out before four parts exist, the branch is dead.
You can cut such branches early: if the digits left are fewer than the parts still needed, or more than three times as many, stop. Join the parts with dots when saving.
left = len(s) - i need = 4 - parts
Why is the piece 01 not allowed?
- AA part with more than one digit may not start with 0
- BIt is larger than 255
- CIt has an odd number of digits
Show the answer
A part with more than one digit may not start with 0. Only the single digit 0 is allowed to begin with zero.
Restore IP addresses
A valid IP address is four numbers from 0 to 255, written without leading zeros, separated by dots. Given a string s of digits, return all the valid IP addresses that can be made by putting three dots into s, without reordering or removing any digit. List them in the order found by trying shorter parts before longer ones, from left to right.
s = "25525511135" → ["255.255.11.135", "255.255.111.35"]
0 ≤ length of s ≤ 20 · s has only digits