समस्या विवरण
मान लीजिए एक प्रोग्राम है जो सरणी A के तत्वों को प्रिंट करने के लिए उपयोग किया जाता है, लेकिन उस प्रोग्राम में एक छोटी गलती थी। उस प्रोग्राम में प्रत्येक तत्व के बाद कोई व्हाइटस्पेस नहीं था, इसलिए यदि हमारे पास एक प्रिंटेड स्ट्रिंग है, तो क्या हम सरणी को फिर से उत्पन्न कर सकते हैं? हम जानते हैं कि सरणी के तत्व 1 से k की रेंज में हैं।
स्ट्रिंग s और पूर्णांक k दिया गया है। हमें ज्ञात करना है कि हम कितने तरीकों से सरणी को पुनर्स्थापित कर सकते हैं। उत्तर बहुत बड़ा हो सकता है इसलिए इसे 10^9 + 7 से मॉड्यूलो करके लौटाएं।
उदाहरण
यदि इनपुट है: S = "1318" और k = 2000, तो आउटपुट होगा 8, क्योंकि हम 8 अलग-अलग सरणियाँ बना सकते हैं जैसे [1318], [131,8], [13,18], [1,318], [1,3,18], [1,31,8], [13,1,8], [1,3,1,8]
हल करने का दृष्टिकोण
इस समस्या को हल करने के लिए निम्नलिखित चरणों का पालन करें (डायनामिक प्रोग्रामिंग):
- const int m = 1e9 + 7
- एक मैप dp परिभाषित करें
- add() नामक एक फ़ंक्शन परिभाषित करें, जो a, b लेता है:
- ((a % m) + (b % m)) % m लौटाएं
- help() नामक एक फ़ंक्शन परिभाषित करें, जो idx, s, num, k लेता है:
- यदि idx >= s का आकार, तो 1 लौटाएं
- यदि idx, dp में है और num, dp[idx] में है:
- dp[idx][num] लौटाएं
- ret := 0
- यदि num >= 1 और num <= k और s[idx] '0' के बराबर नहीं है:
- ret := add(help(idx, s, 0, k), ret)
- यदि num * 10 + (s[idx] - '0') <= k:
- ret := add(help(idx + 1, s, num * 10 + (s[idx] - '0'), k), ret)
- dp[idx][num] := ret
- ret लौटाएं
- मुख्य विधि से:
- n := s का आकार
- आकार n + 1 की एक सरणी ans परिभाषित करें
- ans[0] := 1
- s := s से पहले एक व्हाइटस्पेस जोड़ें
- ks := k को स्ट्रिंग में बदलें
- i := 1 से आरंभ करें, जब i <= n, i को 1 से बढ़ाते हुए:
- cnt := 1
- temp := खाली स्ट्रिंग
- j := i से आरंभ करें, जब j >= 1 और cnt <= 10, j को 1 से घटाते हुए, cnt को 1 से बढ़ाते हुए:
- temp := s[j] + temp
- यदि s[j] '0' के समान है:
- अगले पुनरावृत्ति पर जाएं
- यदि temp का आकार > ks का आकार:
- लूप से बाहर निकलें
- val := temp को संख्या के रूप में
- यदि val >= 1 और val <= k:
- ans[i] := add(ans[i], ans[j - 1])
- ans[n] लौटाएं
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int m = 1e9 + 7;
class Solution {
public:
unordered_map<int, unordered_map<lli, int>> dp;
lli add(lli a, lli b) {
return ((a % m) + (b % m)) % m;
}
int help(int idx, string& s, lli num, int k) {
if (idx >= s.size())
return 1;
if (dp.count(idx) && dp[idx].count(num))
return dp[idx][num];
int ret = 0;
if (num >= 1 && num <= k && s[idx] != '0') {
ret = add(help(idx, s, 0, k), ret);
}
if (num * 10 + (s[idx] - '0') <= k) {
ret = add(help(idx + 1, s, num * 10 + (s[idx] - '0'), k), ret);
}
return dp[idx][num] = ret;
}
int numberOfArrays(string s, int k) {
int n = s.size();
vector<lli> ans(n + 1);
ans[0] = 1;
s = " " + s;
string ks = to_string(k);
for (lli i = 1; i <= n; i++) {
lli cnt = 1;
string temp = "";
for (lli j = i; j >= 1 && cnt <= 10; j--, cnt++) {
temp = s[j] + temp;
if (s[j] == '0')
continue;
if (temp.size() > ks.size())
break;
lli val = stol(temp);
if (val >= 1 && val <= k) {
ans[i] = add(ans[i], ans[j - 1]);
}
}
}
return ans[n];
}
};
int main() {
Solution ob;
cout << (ob.numberOfArrays("1318", 2000));
return 0;
}
इनपुट
"1318", 2000
आउटपुट
8