Given a string of digits, generate all possible valid IPv4 addresses by inserting three dots into the string. Each segment between dots must be an integer between 0 and 255 (inclusive), must not have leading zeros unless the segment is exactly 0, and the order of digits must be preserved. Return all valid IP addresses as a list of strings. The order of the output does not matter.
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: Two valid IP addresses can be formed.
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.162.5.41","172.162.54.1"]
Case 2
Input: "222255255"
Expected: ["222.255.2.55","222.255.25.5","222.255.255.5"]
Case 3
Input: "000255"
Expected: ["0.0.0.255"]