Implement restoreIpAddresses(s), where s is a string of digits. By placing exactly three dots into s, it is cut into four pieces; return all the ways of doing this that produce a valid IPv4 address.
For the result to be valid, every one of the four pieces has to satisfy these rules:
0 and 255 inclusive;"0" on its own is fine, but "00" and "01" are not;s, keeping the original order.List the valid addresses in depth-first enumeration order, one address per entry. If not a single valid address can be formed, the result is empty.
Example 1:
Input:
25525511135
Output:
2
255.255.11.135
255.255.111.35
Explanation: The first line is the number of valid addresses. These are the only two ways to split the digits into four pieces that each fall in 0–255 without leading zeros.
Example 2:
Input:
010010
Output:
2
0.10.0.10
0.100.1.0
Explanation: Each 0 that begins a piece must stand alone as the piece "0", which leaves exactly these two valid splits.
Example 3:
Input:
0000
Output:
1
0.0.0.0
Explanation: The only possible split uses four pieces "0", each of which is valid on its own.
Example 4:
Input:
300000
Output:
0
Explanation: Every way of cutting 300000 into four pieces produces a piece above 255 (such as 300) or a piece with a leading zero (such as 00), so no valid address exists and the count is 0.
Constraints:
4 <= len(s) <= 12s is composed only of the digits '0' through '9'.Suppose the string must instead be split into some arbitrary given number k of numeric pieces, each still obeying the same value range and leading-zero rules. How would you adapt your algorithm?