1977. Number of Ways to Separate Numbers LeetCode Solution
In this guide, you will get 1977. Number of Ways to Separate Numbers LeetCode Solution with the best time and space complexity. The solution to Number of Ways to Separate Numbers problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Number of Ways to Separate Numbers
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 <= 3500
num consists of digits '0' through '9'.
Complexity Analysis
Time Complexity:
Space Complexity:
1977. Number of Ways to Separate Numbers LeetCode Solution in C++
class Solution {
public:
int numberOfCombinations(string num) {
if (num[0] == '0')
return 0;
constexpr int kMod = 1'000'000'007;
const int n = num.size();
// dp[i][k] := the number of possible lists of integers ending in num[i]
// with the length of the last number being 1..k
vector<vector<long>> dp(n, vector<long>(n + 1));
// lcs[i][j] := the number of the same digits in num[i..n) and num[j..n)
vector<vector<int>> lcs(n + 1, vector<int>(n + 1));
for (int i = n - 1; i >= 0; --i)
for (int j = i + 1; j < n; ++j)
if (num[i] == num[j])
lcs[i][j] = lcs[i + 1][j + 1] + 1;
for (int i = 0; i < n; ++i)
for (int k = 1; k <= i + 1; ++k) {
dp[i][k] += dp[i][k - 1];
dp[i][k] %= kMod;
// The last number is num[s..i].
const int s = i - k + 1;
if (num[s] == '0')
// the number of possible lists of integers ending in num[i] with the
// length of the last number being k
continue;
if (s == 0) {
// the whole string
dp[i][k] += 1;
continue;
}
if (s < k) {
// The length k is not enough, so add the number of possible lists of
// integers in num[0..s - 1].
dp[i][k] += dp[s - 1][s];
continue;
}
const int l = lcs[s - k][s];
if (l >= k || num[s - k + l] <= num[s + l])
// Have enough length k and num[s - k..s - 1] <= num[j..i].
dp[i][k] += dp[s - 1][k];
else
// Have enough length k but num[s - k..s - 1] > num[j..i].
dp[i][k] += dp[s - 1][k - 1];
}
return dp[n - 1][n] % kMod;
}
}; /* code provided by PROGIEZ */
1977. Number of Ways to Separate Numbers LeetCode Solution in Java
class Solution {
public int numberOfCombinations(String num) {
if (num.charAt(0) == '0')
return 0;
final int kMod = 1_000_000_007;
final int n = num.length();
// dp[i][k] := the number of possible lists of integers ending in num[i] with
// the length of the last number being 1..k
long[][] dp = new long[n][n + 1];
// lcs[i][j] := the number of the same digits in num[i..n) and num[j..n)
int[][] lcs = new int[n + 1][n + 1];
for (int i = n - 1; i >= 0; --i)
for (int j = i + 1; j < n; ++j)
if (num.charAt(i) == num.charAt(j))
lcs[i][j] = lcs[i + 1][j + 1] + 1;
for (int i = 0; i < n; ++i)
for (int k = 1; k <= i + 1; ++k) {
dp[i][k] += dp[i][k - 1];
dp[i][k] %= kMod;
// The last number is num[s..i].
final int s = i - k + 1;
if (num.charAt(s) == '0')
// the number of possible lists of integers ending in num[i] with the
// length of the last number being k
continue;
if (s == 0) {
// the whole string
dp[i][k] += 1;
continue;
}
if (s < k) {
// The length k is not enough, so add the number of possible lists of
// integers in num[0..s - 1].
dp[i][k] += dp[s - 1][s];
continue;
}
final int l = lcs[s - k][s];
if (l >= k || num.charAt(s - k + l) <= num.charAt(s + l))
// Have enough length k and num[s - k..s - 1] <= num[j..i].
dp[i][k] += dp[s - 1][k];
else
// Have enough length k but num[s - k..s - 1] > num[j..i].
dp[i][k] += dp[s - 1][k - 1];
}
return (int) dp[n - 1][n] % kMod;
}
} // code provided by PROGIEZ
1977. Number of Ways to Separate Numbers LeetCode Solution in Python
class Solution:
def numberOfCombinations(self, num: str) -> int:
if num[0] == '0':
return 0
kMod = 1_000_000_007
n = len(num)
# dp[i][k] := the number of possible lists of integers ending in num[i]
# with the length of the last number being 1..k
dp = [[0] * (n + 1) for _ in range(n)]
# lcs[i][j] := the number of the same digits in num[i..n) and num[j..n)
lcs = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n - 1, -1, -1):
for j in range(i + 1, n):
if num[i] == num[j]:
lcs[i][j] = lcs[i + 1][j + 1] + 1
for i in range(n):
for k in range(1, i + 2):
dp[i][k] += dp[i][k - 1]
dp[i][k] %= kMod
# The last number is num[s..i].
s = i - k + 1
if num[s] == '0':
# the number of possible lists of integers ending in num[i] with the
# length of the last number being k
continue
if s == 0: # the whole string
dp[i][k] += 1
continue
if s < k:
# The length k is not enough, so add the number of possible lists of
# integers in num[0..s - 1].
dp[i][k] += dp[s - 1][s]
continue
l = lcs[s - k][s]
if l >= k or num[s - k + l] <= num[s + l]:
# Have enough length k and num[s - k..s - 1] <= num[j..i].
dp[i][k] += dp[s - 1][k]
else:
# Have enough length k but num[s - k..s - 1] > num[j..i].
dp[i][k] += dp[s - 1][k - 1]
return dp[n - 1][n] % kMod # code by PROGIEZ
