ধরুন আমাদের কাছে শব্দের একটি তালিকা আছে, আমরা একটি রেফারেন্স স্ট্রিং S এবং সূচী A-এর একটি তালিকা লিখে এটিকে এনকোড করতে পারি। সুতরাং উদাহরণ স্বরূপ, আসুন বিবেচনা করা যাক শব্দের তালিকা ["সময়", "me", "bell" ], তাহলে আমরা এটিকে S ="time#bell#" এবং সূচক =[0, 2, 5] হিসাবে লিখতে পারি। এখানে প্রতিটি সূচকের জন্য, আমরা "#" চিহ্নে না পৌঁছানো পর্যন্ত সেই সূচকের রেফারেন্স স্ট্রিং থেকে পড়ে শব্দটি পুনরুদ্ধার করব।
সুতরাং আমাদের খুঁজে বের করতে হবে যে প্রদত্ত শব্দগুলিকে এনকোড করে এমন সংক্ষিপ্ততম রেফারেন্স স্ট্রিং S এর দৈর্ঘ্য কত? সুতরাং প্রদত্ত উদাহরণের জন্য, আউটপুট হবে 10।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- insertNode পদ্ধতি সংজ্ঞায়িত করুন, এটি হেড এবং স্ট্রিং s লাগবে
- curr :=মাথা, পতাকা :=মিথ্যা।
- এর জন্য s-এর রেঞ্জ সাইজ 1 থেকে 0
- x :=s[i]
- যদি curr-এর m[x] শূন্য হয়, তাহলে ফ্ল্যাট সেট করুন :=true এবং curr-এর m[x]-এ একটি নতুন নোড তৈরি করুন।
- curr :=curr এর m[x]
- পতাকা সত্য হলে s এর আকার ফেরত দিন, অন্যথায় 0
- প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
- ret :=0, head :=নতুন নোড
- শব্দের দৈর্ঘ্যের উপর ভিত্তি করে অ্যারে সাজান
- n :=শব্দের আকার
- আমি 0 থেকে n – 1
- পরিসরে
- temp :=insertNode(head, words[i])
- যদি temp 0 না হয়, তাহলে ret :=ret + temp + 1
- রিটার্ন রিটার্ন।
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
struct Node{
map <char, Node*> m;
};
class Solution {
public:
static bool cmp(string a, string b){
return a.size() > b.size();
}
int insertNode(Node* head, string s){
Node* curr = head;
bool flag = false;
for(int i = s.size() - 1; i >= 0; i--){
char x = s[i];
if(!curr->m[x]){
flag = true;
curr->m[x] = new Node();
}
curr = curr->m[x];
}
return flag? (int)s.size() : 0;
}
int minimumLengthEncoding(vector<string>& words) {
int ret = 0;
Node* head = new Node();
sort(words.begin(), words.end(), cmp);
int n = words.size();
for(int i = 0; i < n; i++){
int temp= insertNode(head, words[i]);
if(temp){
ret += (temp + 1);
}
}
return ret;
}
};
main(){
vector<string> v = {"time", "me", "bell"};
Solution ob;
cout << (ob.minimumLengthEncoding(v));
} ইনপুট
["time", "me", "bell"]
আউটপুট
10
