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 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. There can be multiple ways to restore the array.
Return the number of possible array that can be printed as a string s using the mentioned program.
The number of ways could be very large so return it modulo 10^9 + 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]
Example 4:
Input: s = "2020", k = 30 Output: 1 Explanation: The only possible array is [20,20]. [2020] is invalid because 2020 > 30. [2,020] is ivalid because 020 contains leading zeros.
Example 5:
Input: s = "1234567890", k = 90 Output: 34
Constraints:
1 <= s.length <= 10^5.sconsists of only digits and doesn’t contain leading zeros.1 <= k <= 10^9.
Solution: DP
dp[i] := # of ways to restore the array for s[i:n].
dp[i] = sum(dp[j]), where 0 < j < n, int(s[i:j]) <= k, s[i] != 0
Time complexity: O(n*logk)
Space complexity: O(n)
Top-down
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua class Solution { public: int numberOfArrays(string s, int k) { constexpr int kMod = 1e9 + 7; const int n = s.length(); vector<int> mem(n, -1); // dp(i) returns # of ways for s[i:n] function<int(int)> dp = [&](int i) { if (i == n) return 1; if (s[i] == '0') return 0; if (mem[i] >= 0) return mem[i]; long num = 0; int ans = 0; for (int j = i + 1; j <= n; ++j) { num = num * 10 + (s[j - 1] - '0'); if (num > k) break; ans = (ans + dp(j)) % kMod; } return mem[i] = ans; }; return dp(0); } }; |
bottom-up
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua class Solution { public: int numberOfArrays(string s, int k) { constexpr int kMod = 1e9 + 7; const int n = s.length(); vector<int> dp(n + 1); // # of ways for s[i:n] dp.back() = 1; for (int i = n - 1; i >= 0; --i) { if (s[i] == '0') continue; long num = 0; for (int j = i + 1; j <= n; ++j) { num = num * 10 + (s[j - 1] - '0'); if (num > k) break; dp[i] = (dp[i] + dp[j]) % kMod; } } return dp[0]; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment