मान लीजिए हमारे पास समानार्थी शब्दों के जोड़ों की सूची synonyms और एक वाक्य text है, हमें लेक्सिकोग्राफिकली सॉर्टेड सभी संभावित समानार्थी वाक्य ढूंढने हैं।
इसलिए, यदि इनपुट है synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]], और text = "I am happy today but was sad yesterday", तो आउटपुट होगा ["I am cheerful today but was sad yesterday", "I am cheerful today but was sorrow yesterday", "I am happy today but was sad yesterday", "I am happy today but was sorrow yesterday", "I am joy today but was sad yesterday", "I am joy today but was sorrow yesterday"]
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
मैप्स parent, color और groupByColor परिभाषित करें
एक फ़ंक्शन find() परिभाषित करें, जो s लेगा,
यदि parent[s], s के समान है, तो -
parent[s] := find(parent[s])
parent[s] लौटाएं
एक फ़ंक्शन unionNode() परिभाषित करें, जो a, b लेगा,
x := find(a), y := find(b)
यदि x, y के समान है, तो -
parent[x] := y
एक ऐरे ans परिभाषित करें
एक फ़ंक्शन getString() परिभाषित करें, जो t लेगा,
एक ऐरे temp परिभाषित करें
end := 0
curr := खाली स्ट्रिंग
end < t के आकार तक, end बढ़ाते हुए, करें -
यदि t[end] खाली स्थान के समान है, तो -
curr को temp के अंत में डालें
curr := खाली स्ट्रिंग
बाकी भाग को अनदेखा करें, अगले इटरेशन पर जाएं
curr := curr + t[end]
curr को temp के अंत में डालें
temp लौटाएं
एक फ़ंक्शन dfs() परिभाषित करें, जो strings, idx, temp (खाली स्ट्रिंग से इनिशियलाइज़) लेगा,
यदि idx, strings के आकार के समान है, तो -
temp को ans के अंत में डालें
लौटें
current := strings[idx]
यदि current, color में नहीं है, तो -
dfs(strings, idx + 1, temp + current + ((यदि idx + 1, strings के आकार के समान है, तो खाली स्ट्रिंग, अन्यथा खाली स्थान)))
अन्यथा
एक सेट x = groupByColor[color[current]] परिभाषित करें
x के प्रत्येक एलिमेंट z के लिए, करें -
dfs(strings, idx + 1, temp + z + ((यदि idx + 1, strings के आकार के समान है, तो खाली स्ट्रिंग, अन्यथा खाली स्थान)))
(z को बढ़ाएं)
एक फ़ंक्शन seeGroups() परिभाषित करें
groupByColor के प्रत्येक एलिमेंट i के लिए, करें -
x := i का दूसरा भाग सेट के रूप में
एक सेट परिभाषित करें
x के प्रत्येक एलिमेंट z के लिए -
(i को बढ़ाएं)
एक फ़ंक्शन generateSentences() परिभाषित करें, जो एक 2D ऐरे s और एक स्ट्रिंग t लेगा,
n := s का आकार
i := 0 से शुरू करें, जब i < n, i बढ़ाते हुए, करें -
x := s[i, 0]
y := s[i, 1]
यदि x, parent में नहीं है, तो -
यदि y, parent में नहीं है, तो -
unionNode(x, y)
c := 1
i := 0 से शुरू करें, जब i < n, i बढ़ाते हुए, करें -
x := s[i, 0]
z := s[i, 1]
y := find(x)
यदि y, color में नहीं है, तो -
color[y] := c
(c को बढ़ाएं)
color[x] := color[y]
color[z] := color[y]
यदि color[x], groupByColor में नहीं है, तो -
एक सेट ss परिभाषित करें
x को ss में डालें
y को ss में डालें
groupByColor[color[x]] := ss
अन्यथा
x को groupByColor[color[x]] में डालें
z को groupByColor[color[x]] में डालें
एक ऐरे strings = getString(t) परिभाषित करें
dfs(strings, 0)
ans ऐरे को सॉर्ट करें
ans लौटाएं
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } class Solution { public: map <string, string> parent; map <string, int> color; map <int, set<string>> groupByColor; string find(string s){ if(parent[s] == s)return s; parent[s] = find(parent[s]); return parent[s]; } void unionNode(string a, string b){ string x = find(a); string y = find(b); if(x == y)return; parent[x] = y; } vector <string> ans; vector <string> getString(string t){ vector <string> temp; int end = 0; string curr = ""; for(;end < t.size(); end++){ if(t[end] == ' '){ temp.push_back(curr); curr = ""; continue; } curr += t[end]; } temp.push_back(curr); return temp; } void dfs(vector <string> &strings, int idx, string temp = ""){ if(idx == strings.size()){ ans.push_back(temp); return; } string current = strings[idx]; if(color.find(current) == color.end()){ dfs(strings, idx + 1, temp + current + (idx+1 == strings.size()?"":" ")); } else{ set <string> x = groupByColor[color[current]]; set <string> :: iterator z = x.begin(); while(z != x.end()){ dfs(strings, idx + 1, temp + *z + (idx+1 == strings.size()?"":" ")); z++; } } } void seeGroups(){ map <int, set <string> > :: iterator i = groupByColor.begin(); while(i != groupByColor.end()){ set <string> x = i->second; set <string> :: iterator z = x.begin(); while(z != x.end()){ z++; } cout << endl; i++; } } vector<string> generateSentences(vector<vector<string>>& s, string t) { int n = s.size(); for(int i = 0; i < n; i++){ string x = s[i][0]; string y = s[i][1]; if(parent.find(x) == parent.end())parent[x] = x; if(parent.find(y) == parent.end())parent[y] = y; unionNode(x,y); } int c = 1; for(int i = 0; i < n; i++){ string x = s[i][0]; string z = s[i][1]; string y = find(x); if(color.find(y) == color.end()){ color[y] = c; c++; } color[x] = color[y]; color[z] = color[y]; if(groupByColor.find(color[x]) == groupByColor.end()){ set <string> ss; ss.insert(x); ss.insert(y); groupByColor[color[x]] = ss; } else{ groupByColor[color[x]].insert(x); groupByColor[color[x]].insert(z); } } vector <string> strings = getString(t); dfs(strings, 0); sort(ans.begin(), ans.end()); return ans; } }; main(){ Solution ob; vector<vector<string>> v = {{"happy","joy"},{"sad","sorrow"},{"joy","cheerful"}}; print_vector(ob.generateSentences(v, "I am happy today but was sad yesterday")); }इनपुट
[["happy","joy"],["sad","sorrow"],["joy","cheerful"]] "I am happy today but was sad yesterday"
आउटपुट
[I am cheerful today but was sad yesterday, I am cheerful today but was sorrow yesterday, I am happy today but was sad yesterday, I am happy today but was sorrow yesterday, I am joy today but was sad yesterday, I am joy today but was sorrow yesterday, ]
