Restore Every Valid IP Address

Problem Statement

Given a string s containing only digits, return all possible valid IPv4 addresses that can be formed by inserting three dots . into s. You must use all digits in s without reordering them, and each dot separates one segment.

A valid IPv4 address consists of exactly four segments separated by single dots. Each segment must satisfy the following conditions:

1. It contains between 1 and 3 digits.
2. Its integer value is in the range [0, 255].
3. It does not contain leading zeros (e.g., "0" is valid, but "01" and "00" are invalid).

Return the list of valid IP addresses sorted in lexicographical order. If no valid IPv4 address can be formed, return an empty list.

Function Signature

def restore_ip_addresses(s: str) -> list[str]:
    pass

Constraints

• 1 <= len(s) <= 20
• s consists only of digits ('0' - '9').

Examples

Example 1

Input: s = "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]
Explanation:
Both partitions produce four valid octets between 0 and 255 without leading zeros.

Example 2

Input: s = "0000"
Output: ["0.0.0.0"]
Explanation:
The only valid configuration splits each digit into its own octet of "0".

Example 3

Input: s = "101023"
Output: ["1.0.10.23", "1.0.102.3", "10.1.0.23", "10.10.2.3", "10.102.0.3", "101.0.2.3"]

Edge Cases

• Strings with length less than 4 or greater than 12 can never form a valid IPv4 address and should immediately return [].
• Octets with value > 255 (such as 256 or 300) must be rejected.
• Single zero ("0") is allowed, but multi-digit segments starting with '0' (e.g., "00", "012") are invalid.