Count Ways to Split String Into Prime Numbers
You are given a string s that represents a positive integer. Count the number of ways to split s into one or more prime numbers.
The digits must remain in the same order, and every digit of s must be used exactly once. Each split part must represent a prime number.
A prime number is an integer greater than 1 that has exactly two positive divisors: 1 and itself.
Method Signature
int countPrimeSplits(String s)
s is the digit string that must be split.- The method returns the number of valid prime-number splits.
- A split part must not be empty.
- A split part with leading zeroes is not considered valid.
Constraints
1 ≤ s.length() ≤ 12s contains only digits from '0' to '9'.s does not start with '0'.- The final answer will fit in a 32-bit signed integer.
Examples
Example 1
Input: countPrimeSplits(s = "3175")
Output: 3
Explanation: The valid splits are [3,17,5], [31,7,5], and [317,5].
Example 2
Input: countPrimeSplits(s = "235")
Output: 2
Explanation: The valid splits are [2,3,5] and [23,5].
Example 3
Input: countPrimeSplits(s = "20")
Output: 0
Explanation: There is no way to split the entire string into only prime numbers.