# Number of Ways to Split Into Primes - Company-specific OAs / Amazon OA

The test used in this challenge for Prime seems wrong,
e.g. test #4:
53739 has 3 ways:
{ ‘5,3,739’, ‘5,3739’, ‘53,739’ }
but the test says 2.

Java solution using DP:

import java.util.ArrayList;
import java.util.List;

public class SplitString {

``````public static int countSplitString(String s) {
int[] dp = new int[s.length() + 1];
for (int i = 0; i < dp.length; i++) {
dp[i] = -1;
}
dp[s.length()] = 1;
return countSplitString(s, 0, dp);
}

private static int countSplitString(String s, int start, int[] dp) {

if (start == s.length()) {
return 0;
}

int count = 0;
for (int i = start; i < s.length() && i < start + 4; i++) {
if (s.charAt(start) != '0') {
String left = s.substring(start, i + 1);
if (isPrime(left)) {
if (dp[i + 1] > -1) {
count += dp[i + 1];
} else {
count += countSplitString(s, i + 1, dp);
}
}
}
}
dp[start] = count;
return count;

}

private static boolean isPrime(String number) {
int num = Integer.valueOf(number);

for (int i = 2; i * i <= num; i++) {
if ((num % i) == 0)
return false;
}
return num > 1 ? true : false;
}
``````

}

Shouldn’t the answer for Test Case #7 be 2? Pretty sure there are two possible partitions: [701, 3] and [7013]

Test case 4 is wrong as pointed by another person.
Test case 7 is also wrong. 7013 is a prime number and the tuple (701, 3) has both numbers also as prime i.e. the answer is 2 instead of 1.

‘5,3739’ has 3739 which is out of bounds.

“Each prime number, pn, must not contain leading 0s, and 2 <= pn <= 1000.”

“Each prime number, pn, must not contain leading 0s, and 2 <= pn <= 1000.”

7013 will violate the constraint.

The title says “Unique”, however, `[3, 11, 7, 3]` contains two `3`.

2 <= pn <= 1000

Java solution using DFS and memoization approach:

import java.util.*;

class Solution {
public static int splitPrimes(String inputStr) {
Map<String, Integer> memo = new HashMap<>();
return helper(inputStr, 0, memo);
}

``````private static int helper(String inputStr, int start, Map<String, Integer> memo) {
if (start == inputStr.length())
return 1;

int count = 0;
for (int i = start; i < inputStr.length(); i++) {
if(inputStr.charAt(start) != '0'){
String str = inputStr.substring(start, i + 1);
Integer value = Integer.parseInt(str);

if (value > 1000)
break;

if (isPrime(value)) {
if (memo.containsKey(inputStr.substring(i + 1))) {
count += memo.get(inputStr.substring(i + 1));
} else {
count += helper(inputStr, i + 1, memo);
}
}
}
}
memo.put(inputStr.substring(start), count);
return count;
}

private static boolean isPrime(int num) {
if (num <= 1)
return false;
if (num == 2 || num == 3)
return true;
if (num % 2 == 0)
return false;

for(int i = 3; i <= Math.sqrt(num); i += 2) {
if (num % i == 0)
return false;
}
return true;
}

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String inputStr = scanner.nextLine();
scanner.close();
int res = splitPrimes(inputStr);
System.out.println(res);
}
``````

}

Python version, using dfs + memo

import math

def split_primes(input_str: str) → int:
def is_prime(n):
if n == 1:
return False
if n ==2 or n == 3:
return True
if n%2 == 0: # even number must not be prime
return False
for i in range(3, int(math.sqrt(n))+1, 2):
if n%i == 0:
return False
return True
# using dfs + memo
def dfs(start_index, memo):
if start_index == len(input_str):
return 1
res = 0
for i in range(start_index, len(input_str)):
if input_str[start_index] != ‘0’:
next_sub_strs = input_str[start_index: i+1]
next_num = int(next_sub_strs)

``````            if next_num > 1000:
break

if is_prime(next_num):
if input_str[i] in memo:
res += memo(input_str[i])
else:
res += dfs(i+1, memo)
memo[start_index] = res
return res

ret = dfs(0, {})
return ret
``````

What is the time complexity of the tabular vs top down DP approach?
I solved for all test cases building from brute force to bottom up DP, but am totally confused about the time complexity. Any leads here?
Here is my code : Playground - LeetCode