আমাদেরকে প্রদত্ত আকারের শব্দগুলির একটি অ্যারে স্ট্রিং দেওয়া হয়েছে এবং কাজটি হল সম্ভাব্য সমস্ত উপায়ে শব্দগুলিকে ভাঙা যাতে বিরতির পরে গঠিত স্ট্রিংটি একটি বৈধ স্ট্রিং হওয়া উচিত এবং আমাদের এই জাতীয় সমস্ত ন্যূনতম শব্দ বিরতি গণনা করতে হবে সমস্যা।
আসুন এর জন্য বিভিন্ন ইনপুট আউটপুট পরিস্থিতি দেখি -
এ − স্ট্রিং শব্দ[] ={"হ্যালো", "হেল", "টেল", "ওয়েল", "বেল", "বল", "সব" }
আউট − ন্যূনতম শব্দ বিরতি হল:1
ব্যাখ্যা - আমাদের একাধিক শব্দ দিয়ে দেওয়া হয়। এখন আমরা দুটি স্ট্রিং অর্থাৎ নরক এবং সকলের সংমিশ্রণ অতিক্রম করব এবং সংযুক্ত শব্দটি ভেঙে দেব। সুতরাং, Hellall কে "Hellall" হিসাবে ভাগ করা যেতে পারে যেটি প্রথম বিরতি এবং উভয় শব্দই বৈধ। এখন, আমরা এটিকে আরও ভেঙ্গে দেব যেমন "He ll aa" যা কোনো বৈধ স্ট্রিং গঠন করছে না। সুতরাং আউটপুট হল 1.
এ − স্ট্রিং শব্দ[] ={"হ্যালো", "হেল", "টেল", "ওয়েল", "বেল", "বল", "সব" }
আউট − ন্যূনতম শব্দ বিরতি হল:1
ব্যাখ্যা - আমাদের একাধিক শব্দ দিয়ে দেওয়া হয়। এখন আমরা দুটি স্ট্রিং এর সংমিশ্রণকে পাস করব যেমন নরক এবং ভাল এবং সংযুক্ত শব্দটি ভেঙে দেব। সুতরাং, হেলওয়েলকে "হেল ওয়েল" হিসাবে ভাগ করা যেতে পারে যেটি প্রথম বিরতি এবং উভয় শব্দই বৈধ। এখন, আমরা এটিকে আরও ভেঙ্গে দেব যেমন "সে ভাল করবে" যা কোনও বৈধ স্ট্রিং তৈরি করছে না। সুতরাং আউটপুট হল 1.
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
শব্দের স্ট্রিং অ্যারে ইনপুট করুন এবং size() ফাংশন ব্যবহার করে আকার গণনা করুন।
-
একটি ভেরিয়েবলকে min_val হিসাবে ঘোষণা করুন এবং সর্বাধিক সম্ভাব্য মান হিসাবে এটিকে INT_MAX এ সেট করুন৷
-
রুট হিসাবে টাইপ স্ট্রাকচারের একটি বস্তু তৈরি করুন এবং Return_Node()
ফাংশনে কল করতে সেট করুন -
একটি অ্যারের আকার পর্যন্ত i থেকে 0 পর্যন্ত লুপ শুরু করুন। লুপের ভিতরে, একটি গাছে নোড ঢোকানোর জন্য Insert_Node() ফাংশনটিকে কল করুন।
-
সম্ভাব্য ন্যূনতম শব্দ বিরতি গণনা করতে Minimum_Break() এ কল করুন এবং চূড়ান্ত ফলাফল প্রিন্ট করুন।
-
ডেটা হিসাবে শব্দ সহ নোডের ট্রি তৈরি করার জন্য একটি কাঠামো ঘোষণা করুন।
-
ptr[total_Alpha] হিসাবে পয়েন্টারগুলির একটি অ্যারে এবং চেক হিসাবে একটি বুলিয়ান ভেরিয়েবল তৈরি করুন৷
-
-
Return_Node(void)
এর ভিতরে-
ptr_1 হিসাবে টাইপ কাঠামোর একটি পয়েন্টার তৈরি করুন। ptr_1->চেক মিথ্যা হিসাবে সেট করুন
-
স্টার্ট লুপ FOR i থেকে 0 পর্যন্ত i যতক্ষণ না মোট_আলফার থেকে কম। লুপের ভিতরে, ptr_1->ptr[i] NULL
সেট করুন -
ptr_1
ফেরত দিন
-
-
ফাংশনের ভিতরে Insert_Node(struct node* root, string val)
-
ptr_1 হিসাবে একটি পয়েন্টার তৈরি করুন এবং এটিকে রুটে সেট করুন।
-
i থেকে 0 থেকে val.length() পর্যন্ত লুপ শুরু করুন। লুপের ভিতরে, val[i] - 'a' হিসাবে কী সেট করুন এবং ptr_1->ptr[key] NULL হলে চেক করুন তারপর ptr_1->ptr[key] ফাংশন Return_Node() এর কলে সেট করুন।
-
ptr_1-এ ptr_1->ptr[কী] সেট করুন এবং ptr_1->সত্যে চেক করুন
-
-
ফাংশনের ভিতরে Minimum_Break(struct node* root, string val, int first, int*temp, int a =0)
-
ptr_1 হিসাবে একটি পয়েন্টার তৈরি করুন এবং এটিকে রুটে সেট করুন।
-
প্রথমে IF =val.length() চেক করুন তারপর C++ এর অন্তর্নির্মিত ফাংশনে কল করার জন্য *temp সেট করুন যা min(*temp, a - 1) এবং রিটার্ন করুন।
-
i থেকে প্রথম পর্যন্ত লুপ শুরু করুন যতক্ষণ না আমি একটি ভ্যালের দৈর্ঘ্যের চেয়ে কম হয়। লুপের ভিতরে, ঠিকানাটি val[i] - 'a' হিসাবে সেট করুন এবং চেক করুন IF ptr_1->ptr[address] শূন্য তারপর ফিরে আসুন।
-
ptr_1->ptr[ঠিকানা]->চেকটি সত্য কিনা তা পরীক্ষা করুন তারপর মিনিমাম_ব্রেক (root, val, i + 1, temp, a + 1) কল করুন
-
ptr_1-এ ptr_1->ptr[ঠিকানা] সেট করুন।
-
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
#define total_Alpha 26
//create a tree of nodes of words
struct node{
struct node* ptr[total_Alpha];
bool check;
};
//Return tree with all nodes
struct node* Return_Node(void){
struct node* ptr_1 = new node;
ptr_1->check = false;
for (int i = 0; i < total_Alpha; i++){
ptr_1->ptr[i] = NULL;
}
return ptr_1;
}
//insert values to the nodes in a tree
void Insert_Node(struct node* root, string val){
struct node* ptr_1 = root;
for(int i = 0; i < val.length(); i++){
int key = val[i] - 'a';
if(!ptr_1->ptr[key]){
ptr_1->ptr[key] = Return_Node();
}
ptr_1 = ptr_1->ptr[key];
}
ptr_1->check = true;
}
//calculate the minimum word break
void Minimum_Break(struct node* root, string val, int first, int* temp, int a = 0){
struct node* ptr_1 = root;
if(first == val.length()){
*temp = min(*temp, a - 1);
return;
}
for(int i = first; i < val.length(); i++){
int address = val[i] - 'a';
if(!ptr_1->ptr[address]){
return;
}
if(ptr_1->ptr[address]->check){
Minimum_Break(root, val, i + 1, temp, a + 1);
}
ptr_1 = ptr_1->ptr[address];
}
}
int main(){
string word[] = {"Hello", "Hell", "tell", "well", "bell", "ball", "all" };
int size = sizeof(word) / sizeof(word[0]);
int min_val = INT_MAX;
struct node* root = Return_Node();
for (int i = 0; i < size; i++){
Insert_Node(root, word[i]);
}
Minimum_Break(root, "Hellall", 0, &min_val, 0);
cout<<"Minimum Word Break is: "<< min_val;
return 0;
} আউটপুট
যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট তৈরি করবে
Minimum Word Break is: 1
