मान लीजिए हमारे पास फ्रेज़ेज़ की एक लिस्ट है, बिफोर एंड आफ्टर पजल्स की एक लिस्ट जनरेट करें। यहां एक फ्रेज़ एक स्ट्रिंग है जिसमें केवल लोअरकेस लेटर्स और स्पेसेस होते हैं। शुरुआत और अंत में कोई स्पेस नहीं होगा। एक फ्रेज़ में कोई लगातार स्पेसेस नहीं होंगे।
बिफोर एंड आफ्टर पजल्स वे फ्रेज़ेज़ हैं जो दो फ्रेज़ेज़ को मर्ज करके बनते हैं जहां पहले फ्रेज़ का लास्ट वर्ड दूसरे फ्रेज़ के फर्स्ट वर्ड के समान होता है। हमें वे बिफोर एंड आफ्टर पजल्स ढूंढने हैं जो हर दो फ्रेज़ेज़ phrases[i] और phrases[j] से बन सकते हैं जहां i != j। ध्यान दें कि दो फ्रेज़ेज़ को मैच करने का क्रम मायने रखता है, हम दोनों ऑर्डर्स पर विचार करना चाहते हैं।
हमें डिस्टिंक्ट स्ट्रिंग्स की एक लिस्ट ढूंढनी है जो लेक्सिकोग्राफिकली सॉर्टेड हो। उदाहरण के लिए, अगर इनपुट है phrases = ["mission statement", "a quick bite to eat", "a chip off the old block", "chocolate bar", "mission impossible", "a man on a mission", "block party", "eat my words", "bar of soap"], तो आउटपुट होगा: ["a chip off the old block party", "a man on a mission impossible", "a man on a mission statement", "a quick bite to eat my words", "chocolate bar of soap"]।
इसे हल करने के लिए, हम इन स्टेप्स को फॉलो करेंगे:
स्ट्रिंग्स का एक ऐरे ret डिफाइन करें, phrases ऐरे को सॉर्ट करें
एक मैप m डिफाइन करें, n := phrases ऐरे का साइज
i को 0 से n-1 तक लूप करें:
s := phrases[i], rspace := राइट साइड से ब्लैंक स्पेस का इंडेक्स
i को m में उस लिस्ट में इंसर्ट करें जो rspace नल होने पर s पर रखी गई है, अन्यथा s के सबस्ट्रिंग को rspace + 1 तक ढूंढें
i को 0 से n-1 तक लूप करें:
s := phrases[i], lspace := लेफ्ट साइड से ब्लैंक स्पेस का इंडेक्स
x := जब lspace नल हो तो s, अन्यथा s के सबस्ट्रिंग को 0 से lspace तक ढूंढें
अगर m में x की के रूप में है:
v := m[x]
j को 0 से v के साइज तक लूप करें:
अगर v[j] i नहीं है, तो phrases[v[j]] + s के सबस्ट्रिंग (x के साइज तक) को ret में इंसर्ट करें
ret को सॉर्ट करें
ret के यूनिक को डिलीट करें और ret लौटाएं
उदाहरण (C++)
बेहतर समझ के लिए निम्न इम्प्लीमेंटेशन देखें:
#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:
vector<string> beforeAndAfterPuzzles(vector<string>& phrases) {
vector <string> ret;
sort(phrases.begin(), phrases.end());
unordered_map <string, vector <int> > m;
int n = phrases.size();
for(int i = 0; i < n; i++){
string s = phrases[i];
auto rspace = s.rfind(' ');
m[rspace == string::npos ? s : s.substr(rspace + 1)].push_back(i);
}
for(int i = 0; i < n; i++){
string s = phrases[i];
auto lspace = s.find(' ');
string x = (lspace == string::npos? s : s.substr(0, lspace));
if(m.count(x)){
vector <int>& v = m[x];
for(int j = 0; j < v.size(); j++){
if(v[j] != i){
ret.push_back(phrases[v[j]] + s.substr(x.size()));
}
}
}
}
sort(ret.begin(), ret.end());
ret.erase(unique(ret.begin(), ret.end()), ret.end());
return ret;
}
};
int main(){
vector<string> v = {"mission statement","a quick bite to eat","a chip off the old block","chocolate bar","mission impossible","a man on a mission","block party","eat my words","bar of soap"};
Solution ob;
print_vector(ob.beforeAndAfterPuzzles(v));
}
इनपुट
["mission statement","a quick bite to eat","a chip off the old block","chocolate bar","mission impossible","a man on a mission","block party","eat my words","bar of soap"]
आउटपुट
[a chip off the old block party, a man on a mission impossible, a man on a mission statement, a quick bite to eat my words, chocolate bar of soap, ]
