Sponsored
Sponsored
This approach uses dynamic programming to solve the problem. The main idea is to keep a dp array where dp[i] represents the number of ways to partition the substring s[0...i] into valid numbers less than or equal to k.
We iterate over the string s, and for each position, we try to form numbers ending at that position by taking substrings of varying lengths. If a substring is valid, we update the dp array.
Time Complexity: O(n * min(n, log10(k)))
Space Complexity: O(n)
1#include <vector>
2#include <string>
3using namespace std;
4
5int numberOfArrays(string s, int k) {
6 int mod = 1000000007;
7 int n = s.length();
8 vector<int> dp(n + 1);
9 dp[0] = 1;
10
11 for (int i = 1; i <= n; ++i) {
12 long long num = 0;
13 for (int j = i; j > max(0, i - 10); --j) {
14 num = num + (s[j - 1] - '0') * pow(10, i - j);
15 if (num > k) break;
16 if (s[j - 1] == '0') continue;
17 dp[i] = (dp[i] + dp[j - 1]) % mod;
18 }
19 }
20
21 return dp[n];
22}The C++ solution uses similar logic to the Python solution. It utilizes a vector for storing the dynamic programming results. By iterating over possible partitions dynamically and ensuring that the number constructed is within the range using basic arithmetic operations, it ensures an efficient check, utilizing the same constraint of up to 10 digits due to k's size.
This approach uses recursion with memoization to explore all possible partitions of the string and calculate the number of ways to divide it into valid numbers. It memorizes the results of subproblems to avoid redundant calculations and improve efficiency.
Time Complexity: O(n * log10(k))
Space Complexity: O(n)
1import java.util.HashMap;
2
3
The Java recursive solution with memoization begins by defining a recursive helper function that takes the current index and explores all paths for substring partitioning, caching results with a HashMap to avoid recomputation. The break occurs if a number exceeds k, ensuring efficiency.