C++ এ ধাঁধার আগে এবং পরে

ধরুন আমাদের কাছে বাক্যাংশের একটি তালিকা আছে, আগে এবং পরে ধাঁধার একটি তালিকা তৈরি করুন৷ এখানে একটি বাক্যাংশ একটি স্ট্রিং যা শুধুমাত্র ছোট হাতের অক্ষর এবং স্পেস নিয়ে গঠিত। প্রারম্ভিক এবং শেষ অবস্থানে কোন স্থান থাকবে না। একটি বাক্যাংশে কোনো পরপর স্পেস নেই৷

আগে এবং পরে ধাঁধা হল এমন বাক্যাংশ যা দুটি বাক্যাংশ একত্রিত করে গঠিত হয় যেখানে প্রথম বাক্যাংশের শেষ শব্দটি দ্বিতীয় বাক্যাংশের প্রথম শব্দের মতো। আমাদের আগে এবং পরে ধাঁধাগুলি খুঁজে বের করতে হবে যা প্রতিটি দুটি বাক্যাংশ বাক্যাংশ[i] এবং বাক্যাংশ[j] যেখানে I!=j দ্বারা গঠিত হতে পারে। মনে রাখবেন যে দুটি বাক্যাংশের মিলের ক্রম গুরুত্বপূর্ণ, আমরা উভয় আদেশ বিবেচনা করতে চাই।

আমাদের অভিধানিকভাবে সাজানো স্বতন্ত্র স্ট্রিংগুলির একটি তালিকা খুঁজে পাওয়া উচিত। সুতরাং ইনপুটটি যদি বাক্যাংশের মত হয় =["মিশন বিবৃতি", "এটি দ্রুত কামড় খাওয়ার জন্য", "পুরানো ব্লকের একটি চিপ", "চকলেট বার", "মিশন ইম্পসিবল", "একটি মিশনে একজন ব্যক্তি", " ব্লক পার্টি", "আমার কথা খাও", "সাবানের বার"], তাহলে আউটপুট হবে:["পুরানো ব্লক পার্টির একটি চিপ", "একজন মিশনে অসম্ভব", "একজন মিশন বিবৃতিতে একজন ব্যক্তি ", "আমার কথা খাওয়ার জন্য একটি দ্রুত কামড়", "সাবানের চকোলেট বার"]।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• স্ট্রিং রেটের একটি অ্যারে সংজ্ঞায়িত করুন, বাক্যাংশ অ্যারে সাজান

• একটি মানচিত্র সংজ্ঞায়িত করুন m, n :=বাক্যাংশ অ্যারের আকার

• আমি 0 থেকে n – 1

  পরিসরে

  • s :=বাক্যাংশ[i], rspace :=ডান দিক থেকে ফাঁকা স্থানগুলির সূচক

  • m[যখন rspace null হয়, তারপর s, অন্যথায় s-এর সাবস্ট্রিং rspace + 1 পর্যন্ত খুঁজুন]

• আমি 0 থেকে n – 1

  পরিসরে

  • s :=বাক্যাংশ[i] lspace :=বাম দিক থেকে ফাঁকা স্থানগুলির সূচী

  • x :=যখন lspace null হয়, তারপর s, অন্যথায় 0 থেকে lspace পর্যন্ত s-এর সাবস্ট্রিং খুঁজুন]

  • যদি m কি হিসাবে x থাকে

    • v :=m[x]

    • j এর জন্য রেঞ্জ 0 থেকে v

      এর আকার

      • যদি v[j] আমি না হয়, তাহলে

        • বাক্যাংশ [v[j]] + s এর সাবস্ট্রিং (x এর আকার পর্যন্ত) 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;
   }
};
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, ]