আমাদের যেকোনো দেওয়া আকারের শব্দের একটি স্ট্রিং অ্যারে দেওয়া আছে এবং কাজটি হল শব্দগুলকে সব সম্ভাব্য উপায়ে ব্রেক করা যাতে ব্রেকের পর তৈরি স্ট্রিংটি একটি বৈধ স্ট্রিং হয় এবং আমাদের সমস্যা অনুযায়ী সকল ন্যূনতম ওয়ার্ড ব্রেক গণনা করতে হবে।
বিভিন্ন ইনপুট-আউটপুট পরিস্থিতি দেখে নিই -
ইন - string word[] = {"Hello", "Hell", "tell", "well", "bell", "ball", "all" }
আউট - ন্যূনতম ওয়ার্ড ব্রেক: 1
ব্যাখ্যা - আমাদের একাধিক শব্দ দেওয়া আছে। এখন আমরা দুটি স্ট্রিংর কনক্যাটিনেশন পাস করব অর্থাৎ Hell এবং all এবং কনক্যাটিনেটেড শব্দটি ব্রেক করব। Hellall কে "Hell all" হিসেবে ভাগ করা যায় যা প্রথম ব্রেক এবং দুটি শব্দই বৈধ। এখন এটিকে আরও ব্রেক করব অর্থাৎ "He ll aa" যা কোনো বৈধ স্ট্রিং তৈরি করে না। তাই আউটপুট ১।
ইন - string word[] = {"Hello", "Hell", "tell", "well", "bell", "ball", "all" }
আউট - ন্যূনতম ওয়ার্ড ব্রেক: 1
ব্যাখ্যা - আমাদের একাধিক শব্দ দেওয়া আছে। এখন আমরা দুটি স্ট্রিংর কনক্যাটিনেশন পাস করব অর্থাৎ Hell এবং well এবং কনক্যাটিনেটেড শব্দটি ব্রেক করব। Hellwell কে "Hell well" হিসেবে ভাগ করা যায় যা প্রথম ব্রেক এবং দুটি শব্দই বৈধ। এখন এটিকে আরও ব্রেক করব অর্থাৎ "He ll well" যা কোনো বৈধ স্ট্রিং তৈরি করে না। তাই আউটপুট ১।
নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতি
- শব্দের স্ট্রিং অ্যারে ইনপুট নিন এবং size() ফাংশন ব্যবহার করে আকার গণনা করুন।
- min_val নামের একটি ভেরিয়েবল ডিক্লেয়ার করুন এবং INT_MAX হিসেবে সর্বোচ্চ সম্ভাব্য মান দিয়ে সেট করুন।
- root নামে একটি স্ট্রাকচার অবজেক্ট তৈরি করুন এবং সেটি Return_Node() ফাংশন কল করে সেট করুন।
- i = ০ থেকে অ্যারের আকার পর্যন্ত একটি FOR লুপ শুরু করুন। লুপের ভিতরে Insert_Node() ফাংশন কল করুন ট্রিতে নোড ইনসার্ট করতে।
- Minimum_Break() কল করুন ন্যূনতম ওয়ার্ড ব্রেক সম্ভব গণনা করতে এবং চূড়ান্ত ফলাফল প্রিন্ট করুন।
- শব্দ হিসেবে ডেটা নিয়ে নোডের ট্রি কনস্ট্রাক্ট করার জন্য একটি স্ট্রাকচার ডিক্লেয়ার করুন।
- ptr[total_Alpha] নামে পয়েন্টারের একটি অ্যারে এবং check নামে একটি বুলিয়ান ভেরিয়েবল তৈরি করুন।
- Return_Node(void) ফাংশনের ভিতরে:
- ptr_1 নামে স্ট্রাকচার টাইপের একটি পয়েন্টার তৈরি করুন। ptr_1->check কে false সেট করুন।
- i = ০ থেকে total_Alpha পর্যন্ত একটি FOR লুপ শুরু করুন। লুপের ভিতরে ptr_1->ptr[i] = NULL সেট করুন।
- ptr_1 রিটার্ন করুন।
- Insert_Node(struct node* root, string val) ফাংশনের ভিতরে:
- ptr_1 নামে একটি পয়েন্টার তৈরি করুন এবং root-এ সেট করুন।
- i = ০ থেকে val.length() পর্যন্ত একটি FOR লুপ শুরু করুন। লুপের ভিতরে key = val[i] - 'a' সেট করুন এবং চেক করুন IF ptr_1->ptr[key] is NULL তবে ptr_1->ptr[key] = Return_Node() কল করে সেট করুন।
- ptr_1 = ptr_1->ptr[key] এবং ptr_1->check = true সেট করুন।
- Minimum_Break(struct node* root, string val, int first, int* temp, int a = 0) ফাংশনের ভিতরে:
- ptr_1 নামে একটি পয়েন্টার তৈরি করুন এবং root-এ সেট করুন।
- চেক করুন IF first == val.length() তবে *temp = min(*temp, a - 1) ইনবিল্ট ফাংশন কল করে সেট করুন এবং রিটার্ন করুন।
- i = first থেকে val.length() পর্যন্ত একটি FOR লুপ শুরু করুন। লুপের ভিতরে address = val[i] - 'a' সেট করুন এবং চেক করুন IF ptr_1->ptr[address] is null তবে রিটার্ন করুন।
- চেক করুন IF ptr_1->ptr[address]->check is true তবে Minimum_Break(root, val, i + 1, temp, a + 1) কল করুন।
- ptr_1 = ptr_1->ptr[address] সেট করুন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
#define total_Alpha 26
//শব্দ ডেটা হিসেবে নোডের ট্রি তৈরি
struct node{
struct node* ptr[total_Alpha];
bool check;
};
//সকল নোডসহ ট্রি রিটার্ন
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;
}
//ট্রিতে নোডে মান ইনসার্ট
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;
}
//ন্যূনতম ওয়ার্ড ব্রেক গণনা
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
