Every Valid IPv4 Address Restorable From a Digit String

Implement restorableIpAddresses

Given a string of digits, insert exactly three dots to split it into four parts, each a valid IPv4 segment — a number from 0 to 255 with no leading zero (unless the segment is exactly "0"). Return every distinct address that can be built this way. Trying every combination of four part-lengths and only checking whether they even sum to the right total afterward wastes effort on combinations that could never have worked. Comparing the digits left over to the parts still needed, before ever slicing out a candidate piece, rules out an unworkable length using nothing but arithmetic — no substring built, no validity check run, for a length that was doomed from the start.

Example 1:

Input: digits = "10203040"

Output: ["10.20.30.40","10.203.0.40","102.0.30.40"]

Example 2:

Input: digits = "1111"

Output: ["1.1.1.1"]

Example 3:

Input: digits = "000256"

Output: []

+ 6 hidden test cases run on Submit.

Constraints:

  • 1 ≤ digits.length ≤ 12
  • digits consists only of digits '0'–'9'
  • A valid IPv4 part is 0–255 with no leading zero, unless the part is exactly "0"
  • Results are returned sorted in ascending (lexicographic) order for a stable, checkable answer

digits =

10203040