Restore Valid IP Addresses from a String

Given a string containing only digits, your task is to restore it by splitting it into four valid parts that represent an IPv4 address. An IPv4 address consists of four octets (numbers) separated by dots. Each octet must be a number between 0 and 255, inclusive, and cannot have leading zeros unless it is the number 0 itself.

Problem Description

The goal is to find all possible ways to partition a given string of digits into four valid octets that form a correct IPv4 address.

Key Requirements:

1. Four Octets: The string must be divided into exactly four parts.
2. Valid Octet Range: Each octet must represent an integer from 0 to 255.
3. No Leading Zeros (Except for '0'): An octet cannot have a leading zero if it is a multi-digit number. For example, "01" is invalid, but "0" is valid.
4. All Digits Used: The entire input string must be used, with no remaining characters.
5. Output Format: The output should be a list of strings, where each string is a valid IPv4 address.

Expected Behavior:

If a string can be partitioned in multiple ways to form valid IP addresses, all such valid addresses should be returned. If no valid IP addresses can be formed, an empty list should be returned.

Edge Cases to Consider:

• Strings with fewer than 4 digits (impossible to form 4 octets).
• Strings with more than 12 digits (impossible to form 4 octets, as each octet can be at most 3 digits and the maximum sum of digits is 3*4=12).
• Strings containing digits that would result in octets outside the 0-255 range.
• Strings that would force leading zeros in octets.

Examples

Example 1:

Input: "25525511135"
Output: ["255.255.11.135"]
Explanation: The string can be split into "255", "255", "11", and "135". Each part is a valid octet, and they form a valid IP address.

Example 2:

Input: "0000"
Output: ["0.0.0.0"]
Explanation: The only valid way to split this is into four "0" octets.

Example 3:

Input: "101023"
Output: ["1.0.10.23", "1.0.102.3", "10.1.0.23", "10.10.2.3", "101.0.2.3"]
Explanation: Multiple valid partitions exist, forming different IP addresses.

Example 4:

Input: "010010"
Output: ["0.10.0.10", "0.100.1.0"]
Explanation: Leading zeros need careful handling. "01" is invalid as an octet, but "0" followed by other digits is fine if it forms a valid octet.

Constraints

• The input string s will consist only of digits ('0'-'9').
• The length of s will be between 0 and 3000, inclusive. (Note: While the theoretical maximum length for a valid IP is 12, the constraint is broader to test handling of invalid inputs gracefully).
• The algorithm should be reasonably efficient, aiming for a time complexity that scales well with the input string length.

Notes

• Think about how to systematically explore all possible partitions of the string.
• Consider a recursive or iterative approach to try different splitting points.
• Pay close attention to the conditions for a valid octet: its numerical value and the absence of invalid leading zeros.
• A helper function to check if a substring is a valid octet would be beneficial.