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 109 + 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.
Constraints:
1 <= num.length <= 3500num consists of digits '0' through '9'.
Solutions
Solution 1: Dynamic Programming + Prefix Sum
Define dp[i][j] to represent the number of ways to partition the first i characters of the string num such that the length of the last number is j. Clearly, the answer is ∑_{j=0}n dp[n][j]. The initial value is dp[0][0] = 1.
For dp[i][j], the end of the previous number should be i-j. We can enumerate dp[i-j][k], where k \le j. For the part where k < j, i.e., the number of ways with a length less than j can be directly added to dp[i][j], i.e., dp[i][j] = ∑_{k=0}j-1 dp[i-j][k]. Because the previous number is shorter, it means it is smaller than the current number. Here, prefix sum can be used for optimization.
However, when k = j, we need to compare the sizes of the two numbers of the same length. If the previous number is larger than the current number, this situation is invalid, and we should not add it to dp[i][j]. Otherwise, we can add it to dp[i][j]. Here, we can preprocess the "longest common prefix" in O(n2) time, and then compare the sizes of two numbers of the same length in O(1) time.
The time complexity is O(n2), and the space complexity is O(n2). Where n is the length of the string num.
PythonJavaC++GoTypeScript
class Solution:
def numberOfCombinations(self, num: str) -> int:
def cmp(i, j, k):
x = lcp[i][j]
return x >= k or num[i + x] >= num[j + x]
mod = 10**9 + 7
n = len(num)
lcp = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n - 1, -1, -1):
for j in range(n - 1, -1, -1):
if num[i] == num[j]:
lcp[i][j] = 1 + lcp[i + 1][j + 1]
dp = [[0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
for j in range(1, i + 1):
v = 0
if num[i - j] != '0':
if i - j - j >= 0 and cmp(i - j, i - j - j, j):
v = dp[i - j][j]
else:
v = dp[i - j][min(j - 1, i - j)]
dp[i][j] = (dp[i][j - 1] + v) % mod
return dp[n][n](code-box)
class Solution {
public int numberOfCombinations(String num) {
final int mod = (int) 1e9 + 7;
int n = num.length();
int[][] lcp = new int[n + 1][n + 1];
for (int i = n - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
if (num.charAt(i) == num.charAt(j)) {
lcp[i][j] = 1 + lcp[i + 1][j + 1];
}
}
}
int[][] dp = new int[n + 1][n + 1];
dp[0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= i; ++j) {
int v = 0;
if (num.charAt(i - j) != '0') {
if (i - j - j >= 0) {
int x = lcp[i - j][i - j - j];
if (x >= j || num.charAt(i - j + x) >= num.charAt(i - j - j + x)) {
v = dp[i - j][j];
}
}
if (v == 0) {
v = dp[i - j][Math.min(j - 1, i - j)];
}
}
dp[i][j] = (dp[i][j - 1] + v) % mod;
}
}
return dp[n][n];
}
}(code-box)
class Solution {
public:
int numberOfCombinations(string num) {
const int mod = 1e9 + 7;
int n = num.size();
vector<vector<int>> lcp(n + 1, vector<int>(n + 1));
for (int i = n - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
if (num[i] == num[j]) {
lcp[i][j] = 1 + lcp[i + 1][j + 1];
}
}
}
auto cmp = [&](int i, int j, int k) {
int x = lcp[i][j];
return x >= k || num[i + x] >= num[j + x];
};
vector<vector<int>> dp(n + 1, vector<int>(n + 1));
dp[0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= i; ++j) {
int v = 0;
if (num[i - j] != '0') {
if (i - j - j >= 0 && cmp(i - j, i - j - j, j)) {
v = dp[i - j][j];
} else {
v = dp[i - j][min(j - 1, i - j)];
}
}
dp[i][j] = (dp[i][j - 1] + v) % mod;
}
}
return dp[n][n];
}
};(code-box)
func numberOfCombinations(num string) int {
n := len(num)
lcp := make([][]int, n+1)
dp := make([][]int, n+1)
for i := range lcp {
lcp[i] = make([]int, n+1)
dp[i] = make([]int, n+1)
}
for i := n - 1; i >= 0; i-- {
for j := n - 1; j >= 0; j-- {
if num[i] == num[j] {
lcp[i][j] = 1 + lcp[i+1][j+1]
}
}
}
cmp := func(i, j, k int) bool {
x := lcp[i][j]
return x >= k || num[i+x] >= num[j+x]
}
dp[0][0] = 1
var mod int = 1e9 + 7
for i := 1; i <= n; i++ {
for j := 1; j <= i; j++ {
v := 0
if num[i-j] != '0' {
if i-j-j >= 0 && cmp(i-j, i-j-j, j) {
v = dp[i-j][j]
} else {
v = dp[i-j][min(j-1, i-j)]
}
}
dp[i][j] = (dp[i][j-1] + v) % mod
}
}
return dp[n][n]
}(code-box)
function numberOfCombinations(num: string): number {
const n: number = num.length;
const mod: number = 1_000_000_007;
const lcp: number[][] = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0));
const dp: number[][] = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0));
for (let i = n - 1; i >= 0; i--) {
for (let j = n - 1; j >= 0; j--) {
if (num[i] === num[j]) {
lcp[i][j] = 1 + lcp[i + 1][j + 1];
}
}
}
function cmp(i: number, j: number, k: number): boolean {
const x: number = lcp[i][j];
return x >= k || num[i + x] >= num[j + x];
}
dp[0][0] = 1;
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= i; j++) {
let v: number = 0;
if (num[i - j] !== '0') {
if (i - j - j >= 0 && cmp(i - j, i - j - j, j)) {
v = dp[i - j][j];
} else {
v = dp[i - j][Math.min(j - 1, i - j)];
}
}
dp[i][j] = (dp[i][j - 1] + v) % mod;
}
}
return dp[n][n];
}(code-box)
