Formatted question description: https://leetcode.ca/all/1977.html

# 1977. Number of Ways to Separate Numbers

## Level

Hard

## Description

You wrote down many **positive** integers in a string called `num`

. However, you realized that you forgot to add commas to seperate the different numbers. You remember that the list of integers was **non-decreasing** and that **no** integer had leading zeros.

Return *the number of possible lists of integers that you could have written down to get the string num*. Since the answer may be large, return it

**modulo**

`10^9 + 7`

.**Example 1:**

**Input:** num = “327”

**Output:** 2

**Explanation:** You could have written down the numbers:

3, 27

327

**Example 2:**

**Input:** num = “094”

**Output:** 0

**Explanation:** No numbers can have leading zeros and all numbers must be positive.

**Example 3:**

**Input:** num = “0”

**Output:** 0

**Explanation:** No numbers can have leading zeros and all numbers must be positive.

**Example 4:**

**Input:** num = “9999999999999”

**Output:** 101

**Constraints:**

`1 <= num.length <= 3500`

`num`

consists of digits`'0'`

through`'9'`

.

## Solution

Use dynamic programming with precalculation. First, precalculate the longest common prefixes of each pair of substrings. Next, use dynamic programming to count the number of ways.

```
class Solution {
public int numberOfCombinations(String num) {
final int MODULO = 1000000007;
if (num.charAt(0) == '0')
return 0;
int length = num.length();
int[][] lcp = new int[length][length];
for (int i = length - 1; i >= 0; i--) {
lcp[i][length - 1] = num.charAt(i) == num.charAt(length - 1) ? 1 : 0;
for (int j = i + 1; j < length - 1; j++)
lcp[i][j] = num.charAt(i) == num.charAt(j) ? lcp[i + 1][j + 1] + 1 : 0;
}
int[][] dp = new int[length][length];
for (int i = 0; i < length; i++)
dp[0][i] = 1;
for (int i = 1; i < length; i++) {
if (num.charAt(i) == '0')
continue;
int presum = 0;
for (int j = i; j < length; ++j) {
int range = j - i + 1;
dp[i][j] = presum;
if (i - range >= 0) {
if (lcp[i - range][i] >= range || num.charAt(i - range + lcp[i - range][i]) < num.charAt(i + lcp[i - range][i]))
dp[i][j] = (dp[i][j] + dp[i - range][i - 1]) % MODULO;
presum = (presum + dp[i - range][i - 1]) % MODULO;
}
}
}
int ways = 0;
for (int i = 0; i < length; i++)
ways = (ways + dp[i][length - 1]) % MODULO;
return ways;
}
}
```