सी ++ में पहेली से पहले और बाद में

मान लीजिए कि हमारे पास वाक्यांशों की एक सूची है, पहेलियों से पहले और बाद की सूची तैयार करें। यहां एक वाक्यांश एक स्ट्रिंग है जिसमें केवल लोअरकेस अक्षर और रिक्त स्थान होते हैं। आरंभ और समाप्ति की स्थिति में कोई स्थान नहीं होगा। किसी वाक्यांश में कोई क्रमागत रिक्तियाँ नहीं होती हैं।

पहले और बाद की पहेलियाँ ऐसे वाक्यांश हैं जो दो वाक्यांशों को मिलाकर बनते हैं जहाँ पहले वाक्यांश का अंतिम शब्द दूसरे वाक्यांश के पहले शब्द के समान होता है। हमें पहले और बाद की पहेलियों को खोजना होगा जो हर दो वाक्यांश वाक्यांशों [i] और वाक्यांशों [j] द्वारा बनाई जा सकती हैं जहां I! =j। ध्यान दें कि दो वाक्यांशों के मिलान का क्रम मायने रखता है, हम दोनों आदेशों पर विचार करना चाहते हैं।

हमें लेक्सिकोग्राफिक रूप से छांटे गए अलग-अलग स्ट्रिंग्स की एक सूची मिलनी चाहिए। तो अगर इनपुट वाक्यांशों की तरह है =["मिशन स्टेटमेंट", "ए क्विक बाइट टू ईट", "ए चिप ऑफ ओल्ड ब्लॉक", "चॉकलेट बार", "मिशन इम्पॉसिबल", "ए मैन ऑन अ मिशन", " ब्लॉक पार्टी", "ईट माय वर्ड्स", "बार ऑफ सोप"], तो आउटपुट होगा:["ए चिप ऑफ द ओल्ड ब्लॉक पार्टी", "ए मैन ऑन अ मिशन इम्पॉसिबल", "ए मैन ऑन अ मिशन स्टेटमेंट ", "ए क्विक बाइट टू ईट माई वर्ड्स", "चॉकलेट बार ऑफ सोप"]।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• स्ट्रिंग्स रिट की एक सरणी को परिभाषित करें, वाक्यांशों की सरणी को सॉर्ट करें

• मैप को परिभाषित करें m, n:=वाक्यांशों की सरणी का आकार

• I के लिए 0 से n - 1 की सीमा में

  • s:=वाक्यांश [i], rspace:=दाईं ओर से रिक्त स्थान का सूचकांक

  • एम पर रखी गई सूची में I डालें [जब rspace शून्य है, फिर s, अन्यथा rspace + 1 तक s का विकल्प खोजें]

• I के लिए 0 से n - 1 की सीमा में

  • s :=वाक्यांश [i] lspace :=बाईं ओर से रिक्त स्थानों की अनुक्रमणिका

  • x :=जब lspace रिक्त हो, तब s, अन्यथा s का 0 से lspace में सबस्ट्रिंग ज्ञात करें]

  • अगर m में x की के रूप में है

    • वी:=एम[एक्स]

    • j के लिए 0 से v के आकार की सीमा में

      • अगर v[j] मैं नहीं हूं, तो

        • वाक्यांशों को सम्मिलित करें [v [j]] + s (x के आकार तक) को 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;
   }
};
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, ]