मान लीजिए हमारे पास एक स्ट्रिंग S है जो शब्दों की सूची को दर्शाती है। यहां शब्द में प्रत्येक अक्षर के 1 या अधिक विकल्प होते हैं। यदि केवल एक विकल्प है, तो अक्षर को जैसा है वैसा ही दर्शाया जाता है। यदि एक से अधिक विकल्प हैं, तो कर्ली ब्रेसेस विकल्पों को सीमांकित करते हैं। इसलिए उदाहरण के लिए, "{a,b,c}" विकल्प ["a", "b", "c"] को दर्शाएगा। अब उदाहरण के लिए, अगर इनपुट "{a,b,c}d{e,f}" है तो यह सूची ["ade", "adf", "bde", "bdf", "cde", "cdf"] को दर्शाएगा।
इस तरीके से बनने वाले सभी शब्दों को लेक्सिकोग्राफिकल क्रम में लौटाएं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
ret नामक एक सरणी परिभाषित करें, n नामक एक पूर्णांक प्रकार का चर परिभाषित करें
solve() नामक एक मेथड परिभाषित करें, यह इंडेक्स, लिस्ट और curr को इनपुट के रूप में लेगा
यदि इंडेक्स = n, तो curr को ret में डालें और लौटें
i को 0 से लिस्ट[इंडेक्स] के आकार तक रेंज में लिए:
solve(इंडेक्स + 1, लिस्ट, curr + लिस्ट[इंडेक्स, i]) कॉल करें
मुख्य मेथड से, निम्नलिखित करें:
आकार 100 की एक लिस्ट बनाएं, n := 0 सेट करें, फ्लैग := फाल्स
i को 0 से s के आकार - 1 तक रेंज में लिए:
यदि s[i] कॉमा है, तो अगले इटरेशन पर जाएं
अन्यथा जब s[i] ओपनिंग ब्रेस है, तो फ्लैग := ट्रू सेट करें
अन्यथा जब s[i] क्लोजिंग ब्रेस है, तो फ्लैग := फाल्स सेट करें और n को 1 से बढ़ाएं
अन्यथा लिस्ट[n] को s[i] से बढ़ाएं, अब यदि फ्लैग फाल्स है, तो n को 1 से बढ़ाएं
solve(0, लिस्ट, खाली स्ट्रिंग) कॉल करें
ret सरणी को सॉर्ट करें
ret लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; class Solution { public: vector <string> ret; int n; vector<string> expand(string s) { vector <string> list(100); n = 0; int flag = false; for(int i = 0; i < s.size(); i++){ if(s[i] == ','){ continue; }else if(s[i] == '{'){ flag = true; }else if(s[i] == '}'){ flag = false; n++; }else{ list[n] += s[i]; if(!flag)n++; } } solve(0, list); sort(ret.begin(), ret.end()); return ret; } void solve(int idx, vector <string> list, string curr = ""){ if(idx == n){ ret.push_back(curr); return; } for(int i = 0; i < list[idx].size(); i++){ solve(idx + 1, list, curr + list[idx][i]); } } }; main(){ Solution ob; print_vector(ob.expand("{a,b}c{d,e}f")); }इनपुट
"{a,b}c{d,e}f"आउटपुट
[acdf, acef, bcdf, bcef, ]
