ধরুন আমাদের কাছে শব্দের একটি তালিকা আছে। এই শব্দগুলি স্বতন্ত্র। আমাদের একটি অ্যালগরিদম তৈরি করতে হবে যা শব্দের দেওয়া তালিকায় সমস্ত সংযুক্ত শব্দ খুঁজে পাবে। একটি সংযুক্ত শব্দ আসলে একটি স্ট্রিং যা প্রদত্ত অ্যারেতে কমপক্ষে দুটি ছোট শব্দ নিয়ে গঠিত৷
সুতরাং শব্দগুলো যদি হয় ["গরু", "গরু", "গরুছাগল", "ছাগল", "ছাগলছাগল", "জলপালক", "হরিণ", "হরিণ"], তাহলে আউটপুট হবে ["cowsgoatcows", "ছাগলছাগল", "হরিণের ছাগল"]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি ফাংশন isPresent() সংজ্ঞায়িত করুন, এটি str, head, idx, একটি অ্যারে dp,
- যদি idx>=str এর আকার হয়, তাহলে −
- সত্যে ফিরে আসুন
- যদি dp[idx] -1 এর সমান না হয়, তাহলে −
- রিটার্ন dp[idx]
- একটি নোড curr তৈরি করুন :=head
- ঠিক আছে :=মিথ্যা
- আরম্ভ করার জন্য i :=idx, যখন i
- x :=str[i]
- যদি curr-এর সন্তান[x] না হয়, তাহলে −
- লুপ থেকে বেরিয়ে আসুন
- অন্যথায়
- curr :=curr এর সন্তান[x]
- যদি curr এর End সত্য হয়, তাহলে −
- ঠিক আছে :=ঠিক আছে OR isPresent(str, head, i + 1, dp)
- curr এর
- child[x] :=একটি নতুন নোড তৈরি করুন
- curr :=শব্দ[i]
- যদি curr "" এর মত হয়, তাহলে −
- নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তিতে যান
- কারের একই আকারের একটি অ্যারে ডিপি সংজ্ঞায়িত করুন, এটি -1 দিয়ে পূরণ করুন
- যদি কল করা ফাংশনটি Present (curr, head, 0, dp) অ-শূন্য হয়, তাহলে −
- ret এর শেষে curr ঢোকান
- অন্যথায়
- insertNode(head, curr) ফাংশনটিকে কল করুন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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; } struct Node{ bool isEnd; map <char, Node*> child; Node(){ isEnd = false; } }; class Solution { public: bool isPresent(string str, Node* head, int idx, vector <int>& dp){ if(idx >= str.size())return true; if(dp[idx] != -1)return dp[idx]; Node* curr = head; bool ok = false; for(int i = idx; i < str.size(); i++){ char x = str[i]; if(!curr->child[x]){ break; }else{ curr = curr->child[x]; } if(curr->isEnd){ ok |= isPresent(str, head, i + 1, dp); } } return dp[idx] = ok; } static bool cmp(string s1, string s2){ return s1.size() < s2.size(); } void insertNode(Node* head, string s){ Node* curr = head; for(int i = 0; i < s.size(); i++){ char x = s[i]; if(!curr->child[x]){ curr->child[x] = new Node(); } curr = curr->child[x]; } curr->isEnd = true; } vector<string> findAllConcatenatedWordsInADict(vector<string>& words) { Node* head = new Node(); sort(words.begin(), words.end(), cmp); vector <string> ret; for(int i = 0; i < words.size(); i++){ string curr = words[i]; if(curr=="")continue; vector <int> dp(curr.size(), -1); if(isPresent(curr, head, 0, dp)){ ret.push_back(curr); }else{ insertNode(head, curr); } } return ret; } }; main(){ Solution ob; vector<string> v = {"cow","cows","cowsgoatcows","goat","goatcowsgoat","hippopotamuses","deer","deercowgoatcow"}; print_vector(ob.findAllConcatenatedWordsInADict(v)); }
ইনপুট
{"cow","cows","cowsgoatcows","goat","goatcowsgoat","hippopotamuses","deer","deercowgoatcow"}
আউটপুট
[cowsgoatcows, goatcowsgoat, deercowgoatcow, ]