Welcome to Subscribe On Youtube
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 <= 3500numconsists 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; } } ############ class Solution { private static final int MOD = (int) 1e9 + 7; public int numberOfCombinations(String num) { 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]; } } -
// OJ: https://leetcode.com/problems/number-of-ways-to-separate-numbers/ // Time: O(N^2) // Space: O(N^2) class Solution { long mod = 1e9 + 7, N; vector<vector<long>> lcp, m, msum; long sum(string &s, int i, int prevLen) { if (i >= N || prevLen > N - i - 1) return 0; if (msum[i][prevLen] != -1) return msum[i][prevLen]; long ans = (dp(s, i + prevLen + 1, prevLen + 1) + sum(s, i, prevLen + 1)) % mod; return msum[i][prevLen] = ans; } long dp(string &s, int i, int prevLen = 0) { if (i >= N) return i == N; if (s[i] == '0') return 0; if (m[i][prevLen] != -1) return m[i][prevLen]; long ans = 0; if (prevLen && i + prevLen <= N) { int len = lcp[i - prevLen][i]; if (len >= prevLen || s[i - prevLen + len] < s[i + len]) ans = dp(s, i + prevLen, prevLen); } ans = (ans + sum(s, i, prevLen)) % mod; return m[i][prevLen] = ans; } public: int numberOfCombinations(string s) { if (s[0] == '0') return 0; N = s.size(); lcp.assign(N + 1, vector<long>(N + 1, 0)); m.assign(N + 1, vector<long>(N + 1, -1)); msum.assign(N + 1, vector<long>(N + 1, -1)); for (int i = N - 2; i >= 0; --i) { for (int j = N - 1; j > i; --j) { if (s[i] == s[j]) lcp[i][j] = 1 + lcp[i + 1][j + 1]; } } return dp(s, 0); } }; -
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] -
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] } func min(a, b int) int { if a < b { return a } return b }