मान लीजिए कि हमारे पास शब्दों की एक सूची है, हम इसे एक संदर्भ स्ट्रिंग एस और इंडेक्स ए की सूची लिखकर एन्कोड कर सकते हैं। उदाहरण के लिए, आइए विचार करें कि शब्दों की सूची ["time", "me", "bell" है या नहीं। ], तो हम इसे S ="समय#घंटी#" और अनुक्रमणिका =[0, 2, 5] के रूप में लिख सकते हैं। यहां प्रत्येक इंडेक्स के लिए, हम उस इंडेक्स से संदर्भ स्ट्रिंग से पढ़कर शब्द को पुनर्प्राप्त करेंगे जब तक कि हम "#" प्रतीक तक नहीं पहुंच जाते।
तो हमें यह पता लगाना होगा कि दिए गए शब्दों को एन्कोड करने वाली सबसे छोटी संदर्भ स्ट्रिंग एस की लंबाई क्या है? तो दिए गए उदाहरण के लिए, आउटपुट 10 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- insertNode विधि को परिभाषित करें, यह सिर और स्ट्रिंग s लेगा
- कर्र:=सिर, झंडा:=झूठा।
- i के लिए s – 1 के नीचे के आकार के आकार में 0
- x :=s[i]
- अगर curr का m[x] शून्य है, तो फ्लैट सेट करें:=true और curr के m[x] में एक नया नोड बनाएं।
- कर्र:=एम[x] करी
- झंडा सही होने पर s का आकार लौटाएं, अन्यथा 0
- मुख्य विधि से, निम्न कार्य करें -
- ret :=0, head :=new node
- शब्दों को उनकी लंबाई के आधार पर क्रमबद्ध करें
- n :=शब्दों का आकार
- मैं के लिए 0 से n - 1 की सीमा में
- अस्थायी:=insertNode(सिर, शब्द[i])
- अगर टेम्परेचर नॉन 0 है, तो रिट :=रिट + टेम्प + 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