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