790. Restore IP Addresses — Count Valid Decompositions

Given a string s containing only digits, return the number of valid ways to split s into exactly 4 segments forming a valid IPv4 address. Each segment is an integer in [0, 255] with no leading zeros (except '0' itself). Implement with recursive backtracking.

Input: A string of digits enclosed in double quotes.

Output: Return an integer count.

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: "1111"
Output: 1
Explanation: 1.1.1.1.

Constraints

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

Asked by