Given a string of digits, generate all possible valid IPv4 addresses by inserting three dots into the string. Each segment between dots must be a decimal integer in the range [0, 255], must not have leading zeros unless it is 0, and the order of digits must be preserved. Return all valid IP addresses as strings in any order.
Example 1
Input: "123123123123"
Output: ["123.123.123.123"]
Explanation: Only one valid IP address can be formed from this string.
Example 2
Input: "010010"
Output: ["0.10.0.10","0.100.1.0"]
Explanation: Both addresses are valid as segments do not have leading zeros except for 0.
Example 3
Input: "1111"
Output: ["1.1.1.1"]
Explanation: Only one valid IP address can be formed.
Constraints
Case 1
Input: "172162541"
Expected: ["172.16.25.41","172.16.254.1","172.162.54.1"]
Case 2
Input: "222255255255"
Expected: ["222.255.255.255"]
Case 3
Input: "000255255"
Expected: ["0.0.255.255"]
Case 4
Input: "9999999999"
Expected: []
Case 5
Input: "255255255255"
Expected: ["255.255.255.255"]