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)
1def numberOfArrays(s, k):
2 mod = 10**9 + 7
3 n = len(s)
4 dp = [0] * (n + 1)
5 dp[0] = 1
6
7 for i in range(1, n + 1):
8 num = 0
9 for j in range(i, max(i - 10, 0), -1):
10 num = int(s[j - 1]) * 10**(i - j) + num
11 if num > k:
12 break
13 if s[j - 1] == '0':
14 continue
15 dp[i] = (dp[i] + dp[j - 1]) % mod
16
17 return dp[n]The Python solution defines a function numberOfArrays where a dynamic programming table dp is used to track the number of ways to partition the string up to each index. For each end index i, it checks up to the last 10 digits (as k is very large, we can have up to 10 digits) to ensure the number formed is valid (i.e., not starting with zero unless it's a single digit and <= k). The results are stored in the dp array and modulo operation is used to prevent overflow.
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)
1function numberOfArrays(s, k) {
2 const
The JavaScript solution utilizes a depth-first search (DFS) strategy with memoization. This approach recursively computes valid partitions, storing computed results in the memo object, thus minimizing redundant calculations. Breaking when num exceeds k prevents unnecessary exploration.