এই সমস্যায়, আমাদের একটি অভিধান এবং একটি শব্দ দেওয়া হয়। আমাদের কাজ হল দুটি অভিধান শব্দের সংমিশ্রণ ব্যবহার করে প্রদত্ত ওয়ার্স গঠন করা যায় কিনা তা পরীক্ষা করা৷
প্রদত্ত শব্দ গঠনের সময় শব্দের পুনরাবৃত্তি বৈধ নয়।
সমস্যাটি বোঝার জন্য একটি উদাহরণ দেওয়া যাক,
ইনপুট
dictionary = {“hello”, “tutorials”, “program” , “problem”, “coding”, “point”} word = “tutorialspoint” আউটপুট
yes
ব্যাখ্যা
tutorialspoint is created using tutorials and point.
এই সমস্যাটি সমাধান করার জন্য, আমরা অভিধানের সমস্ত উপাদান একটি উপসর্গ ট্রিতে সংরক্ষণ করব যা সাধারণত একটি trie নামে পরিচিত। এবং তারপর ট্রাই-এ শব্দের উপসর্গ অনুসন্ধান করুন, যদি পাওয়া যায় তবে এটিকে দুই ভাগে ভাগ করুন এবং শব্দের অন্য অংশ অনুসন্ধান করুন। যদি এটি সত্য পাওয়া যায় তবে মিথ্যা ফেরত দিন।
সমাধানের বাস্তবায়ন দেখানোর জন্য প্রোগ্রাম,
উদাহরণ
#include<bits/stdc++.h>
using namespace std;
#define char_int(c) ((int)c - (int)'a')
#define SIZE (26)
struct TrieNode{
TrieNode *children[26];
bool isLeaf;
};
TrieNode *getNode(){
TrieNode * newNode = new TrieNode;
newNode->isLeaf = false;
for (int i =0 ; i< 26 ; i++)
newNode->children[i] = NULL;
return newNode;
}
void insert(TrieNode *root, string Key){
int n = Key.length();
TrieNode * pCrawl = root;
for (int i=0; i<n; i++){
int index = char_int(Key[i]);
if (pCrawl->children[index] == NULL)
pCrawl->children[index] = getNode();
pCrawl = pCrawl->children[index];
}
pCrawl->isLeaf = true;
}
int prefixSearch(struct TrieNode *root, string key){
int pos = -1, level;
struct TrieNode *pCrawl = root;
for (level = 0; level < key.length(); level++){
int index = char_int(key[level]);
if (pCrawl->isLeaf == true)
pos = level;
if (!pCrawl->children[index])
return pos;
pCrawl = pCrawl->children[index];
}
if (pCrawl != NULL && pCrawl->isLeaf)
return level;
}
bool isWordCreated(struct TrieNode* root, string word){
int len = prefixSearch(root, word);
if (len == -1)
return false;
string split_word(word, len, word.length()-(len));
int split_len = prefixSearch(root, split_word);
return (len + split_len == word.length());
}
int main() {
vector<string> dictionary = {"tutorials", "program", "solving", "point"};
string word = "tutorialspoint";
TrieNode *root = getNode();
for (int i=0; i<dictionary.size(); i++)
insert(root, dictionary[i]);
cout<<"Word formation using dictionary is ";
isWordCreated(root, word)?cout<<"possible" : cout<<"not possible";
return 0;
} আউটপুট
Word formation using dictionary is possible
