मान लीजिए हमारे पास संख्याओं और ऑपरेटरों (+, -, *) की एक स्ट्रिंग है। हमें सभी संभावित परिणाम ढूंढने हैं जो संख्याओं और ऑपरेटरों को अलग-अलग तरीकों से ग्रुप करके प्राप्त होते हैं। उदाहरण के लिए, इनपुट "2*3-4*5" के लिए आउटपुट [-34, -14, -10, -10, 10] होगा, क्योंकि:
- (2*(3-(4*5))) = -34
- ((2*3)-(4*5)) = -14
- ((2*(3-4))*5) = -10
- (2*((3-4)*5)) = -10
- (((2*3)-4)*5) = 10
हल करने के चरण
- मेमोइजेशन के लिए एक मैप
memoपरिभाषित करें। - एक रिकर्सिव फ़ंक्शन
solve()बनाएं जो इनपुट स्ट्रिंग लेता है। - एक सरणी
retबनाएं परिणाम स्टोर करने के लिए। - यदि इनपुट
memoमें पहले से मौजूद है, तो उसे लौटाएं। - स्ट्रिंग के प्रत्येक वर्ण के लिए लूप चलाएं।
- यदि वर्ण एक ऑपरेटर (+, -, *) है, तो:
- बाएं भाग के लिए रिकर्सिव कॉल करें:
part1 = solve(input.substr(0, i)) - दाएं भाग के लिए रिकर्सिव कॉल करें:
part2 = solve(input.substr(i+1)) - दोनों भागों के सभी संयोजनों के लिए ऑपरेशन करें और
retमें जोड़ें।
- बाएं भाग के लिए रिकर्सिव कॉल करें:
- यदि
retखाली है (यानी कोई ऑपरेटर नहीं मिला), तो स्ट्रिंग को पूर्णांक में बदलकर लौटाएं। memo[input] = retस्टोर करें और लौटाएं।
C++ उदाहरण
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v) {
cout << "[";
for (int i = 0; i < v.size(); i++) {
cout << v[i] << ", ";
}
cout << "]" << endl;
}
class Solution {
public:
map<string, vector<int>> memo;
vector<int> diffWaysToCompute(string input) {
vector<int> ret;
if (memo.count(input)) return memo[input];
for (int i = 0; i < input.size(); i++) {
if (input[i] == '+' || input[i] == '*' || input[i] == '-') {
vector<int> part1 = diffWaysToCompute(input.substr(0, i));
vector<int> part2 = diffWaysToCompute(input.substr(i + 1));
for (int j = 0; j < part1.size(); j++) {
for (int k = 0; k < part2.size(); k++) {
if (input[i] == '+')
ret.push_back(part1[j] + part2[k]);
else if (input[i] == '*')
ret.push_back(part1[j] * part2[k]);
else
ret.push_back(part1[j] - part2[k]);
}
}
}
}
if (ret.empty())
ret.push_back(stoi(input));
return memo[input] = ret;
}
};
int main() {
Solution ob;
print_vector(ob.diffWaysToCompute("2*3-4*5"));
return 0;
}
इनपुट
"2*3-4*5"
आउटपुट
[-34, -10, -14, -10, 10]