In this guide, you will get 1416. Restore The Array LeetCode Solution with the best time and space complexity. The solution to Restore The Array 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.
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 <= 105
s consists of only digits and does not contain leading zeros.
1 <= k <= 109
class Solution {
public:
int numberOfArrays(string s, int k) {
vector<int> mem(s.length(), -1);
return numberOfArrays(s, 0, k, mem);
}
private:
static constexpr int kMod = 1'000'000'007;
// Returns the number of arrays to restore s[i..n) with k.
int numberOfArrays(const string& s, int i, int k, vector<int>& mem) {
if (i == s.length())
return 1; // an empty string ""
if (s[i] == '0')
return 0; // a leading zero
if (mem[i] != -1)
return mem[i];
int res = 0;
long num = 0;
for (int j = i; j < s.length(); ++j) {
num = num * 10 + (s[j] - '0');
if (num > k)
break;
res = (res + numberOfArrays(s, j + 1, k, mem)) % kMod;
}
return mem[i] = res;
}
}; /* code provided by PROGIEZ */
1416. Restore The Array LeetCode Solution in Java
class Solution {
public:
int numberOfArrays(string s, int k) {
constexpr int kMod = 1'000'000'007;
const int n = s.length();
// dp[i] := the number of arrays to restore s[i..n) with k
vector<int> dp(n + 1);
dp.back() = 1; // an empty string ""
for (int i = n - 1; i >= 0; --i) {
if (s[i] == '0')
continue; // a leading zero
long num = 0;
for (int j = i; j < n; ++j) {
num = num * 10 + (s[j] - '0');
if (num > k)
break;
dp[i] = (dp[i] + dp[j + 1]) % kMod;
}
}
return dp[0];
}
}; // code provided by PROGIEZ
1416. Restore The Array LeetCode Solution in Python
