ধরুন আমাদের একটি ফ্রেজের তালিকা আছে, Before and After পাজলের তালিকা তৈরি করতে হবে। এখানে একটি ফ্রেজ হলো একটি স্ট্রিং যা শুধু ছোট হাতের অক্ষর এবং স্পেস সম্বহ করে। শুরু এবং শেষে কোনো স্পেস থাকবে না। কোনো ফ্রেজে দুটি কমশেস্পেস থাকবে না।
Before and After পাজল হলো দুটি ফ্রেজ মিলিয়ে তৈরি করা ফ্রেজ যেখানে প্রথম ফ্রেজের শেষ শব্দটি দ্বিতীয় ফ্রেজের প্রথম শব্দের সাথে মিলে। আমাদের phrases[i] এবং phrases[j] (যেখানে i != j) প্রতিটি জোড়া থেকে তৈরি হওয়া সকল Before and After পাজল খুঁজে বের করতে হবে। মনে রাখবেন দুটি ফ্রেজ মিলানোর ক্রম গুরুত্বপূর্ণ, আমরা দুভাবেই বিবেচনা করব।
আমাদের স্বতন্ত্র স্ট্রিংগুলোর তালিকা লেক্সিকোগ্রাফিক্যালি সাজিয়ে দিতে হবে। যেন ইনপুট 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 := ডান পাশ থেকে ব্ল্যাঙ্ক স্পেসের ইনডেক্স
- যদি rspace null হয় তবে s, অন্যথায় s-এর rspace+1 পর্যন্ত সাবস্ট্রিং-এ m-এ i ইনসার্ট করুন
- i = 0 থেকে n-1 পর্যন্ত লুপ চালান
- s := phrases[i], lspace := বাম পাশ থেকে ব্ল্যাঙ্ক স্পেসের ইনডেক্স
- x := যদি lspace null হয় তবে s, অন্যথায় s-এর 0 থেকে lspace পর্যন্ত সাবস্ট্রিং
- যদি m-এ x কী থাকে
- v := m[x]
- j = 0 থেকে v-এর আকার পর্যন্ত লুপ চালান
- যদি v[j] != i হয়, তবে phrases[v[j]] + s.substr(x.size()) 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, ]
