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

Problems
1

https://algo.monster/problems/amazon_oa_num_ways_to_split_into_primes

2

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.

3

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;
}

}

4

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

5

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.

6

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

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

7

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

7013 will violate the constraint.

8

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

9

2 <= pn <= 1000

10

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);
}

}

11

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
12

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