Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s.
A valid IP address consists of exactly four integers separated by dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros (except for the number 0 itself).
Example 1:
Input: s = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]
Explanation: The two valid IP addresses are formed by placing dots at different positions.
Example 2:
Input: s = "0000"
Output: ["0.0.0.0"]
Explanation: The only valid IP address is 0.0.0.0.
Example 3:
Input: s = "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 IP addresses can be formed from this string. Note that 01.0.10.23 is invalid because the segment 01 has a leading zero.
1 <= s.length <= 20s consists of digits only.