मान लीजिए कि हमारे पास एक स्ट्रिंग S है जो शब्दों की एक सूची का प्रतिनिधित्व करती है। यहां शब्द के प्रत्येक अक्षर में 1 या अधिक विकल्प हैं। यदि केवल एक ही विकल्प है, तो पत्र को इस रूप में दर्शाया गया है। यदि एक से अधिक विकल्प हैं, तो घुंघराले ब्रेसिज़ विकल्पों को सीमित करते हैं। तो उदाहरण के लिए, "{a,b,c}" विकल्पों का प्रतिनिधित्व करेगा ["a", "b", "c"]। अब उदाहरण के लिए, यदि इनपुट "{a,b,c}d{e,f}" जैसा है तो यह सूची ["ade", "adf", "bde", "bdf", "cde", "सीडीएफ"]।
इस तरह से बनने वाले सभी शब्दों को शब्दावली क्रम में लौटाएं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
रिट नामक एक सरणी को परिभाषित करें, एक पूर्णांक प्रकार चर को परिभाषित करें n
-
एक विधि हल करें () को परिभाषित करें, यह इनपुट के रूप में अनुक्रमणिका, सूची और वक्र लेगा
-
यदि अनुक्रमणिका =n है, तो रिट में curr डालें और वापस लौटें
-
मैं के लिए 0 से सूची के आकार में [सूचकांक]
-
कॉल सॉल्व (इंडेक्स + 1, लिस्ट, कर्व + लिस्ट [इंडेक्स, आई])
-
-
मुख्य विधि से, निम्न कार्य करें
-
आकार 100 की सूची बनाएं, n :=0, ध्वज :=असत्य सेट करें
-
मैं के लिए 0 से लेकर s - 1 के आकार तक के लिए
-
यदि s[i] अल्पविराम है, तो अगले पुनरावृत्ति पर जाएं
-
अन्यथा जब s[i] ब्रेस खोल रहा हो, तो ध्वज सेट करें:=true
-
अन्यथा जब s[i] ब्रेस बंद कर रहा हो, तो ध्वज सेट करें:=असत्य और n को 1 से बढ़ाएँ
-
अन्यथा सूची [n] को s [i] से बढ़ाएँ, अब यदि ध्वज गलत है, तो n को 1 से बढ़ाएँ
-
-
कॉल हल (0, सूची, खाली स्ट्रिंग)
-
रिट सरणी को सॉर्ट करें
-
वापसी रिट
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
#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, ]