222. Restore IP Addresses (Count)

Given a string of digits, return the number of valid IPv4 addresses that can be formed by inserting three dots. Each of the four segments must be 0-255 with no leading zeros (except '0' itself).

Input: A quoted digit string.

Output: Integer — number of valid IP addresses.

Examples

Input: "25525511135"
Output: 2
Explanation: 255.255.11.135 and 255.255.111.35.

Input: "0000"
Output: 1
Explanation: 0.0.0.0.

Input: "101023"
Output: 5
Explanation: 5 valid IPs.

Constraints

• 0<=s.length<=20
• digits only

Asked by