A program was supposed to print an array of integers. The program forgot to print whitespaces and the array is printed as a string of digits s and all we know is that all integers in the array were in the range [1, k] and there are no leading zeros in the array.
Given the string s and the integer k, return the number of the possible arrays that can be printed as s using the mentioned program. Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: s = "1000", k = 10000 Output: 1 Explanation: The only possible array is [1000]
Example 2:
Input: s = "1000", k = 10 Output: 0 Explanation: There cannot be an array that was printed this way and has all integer >= 1 and <= 10.
Example 3:
Input: s = "1317", k = 2000 Output: 8 Explanation: Possible arrays are [1317],[131,7],[13,17],[1,317],[13,1,7],[1,31,7],[1,3,17],[1,3,1,7]
Constraints:
1 <= s.length <= 105s consists of only digits and does not contain leading zeros.1 <= k <= 109This 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.
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.
C++
Time Complexity: O(n * min(n, log10(k)))
Space Complexity: O(n)
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.
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.
JavaScript
Time Complexity: O(n * log10(k))
Space Complexity: O(n)
| Approach | Complexity |
|---|---|
| Dynamic Programming with Substring Checking | Time Complexity: O(n * min(n, log10(k))) |
| Recursive with Memoization | Time Complexity: O(n * log10(k)) |
Rotate Array - Leetcode 189 - Python • NeetCode • 192,989 views views
Watch 9 more video solutions →Practice Restore The Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor