मान लीजिए हमारे पास n अद्वितीय स्ट्रिंग्स की एक सरणी है, हमें नीचे दिए गए नियमों का पालन करते हुए हर शब्द के लिए न्यूनतम संभव संक्षिप्तीकरण उत्पन्न करना है।
- पहले वर्ण से शुरू करें और फिर संक्षिप्त किए गए वर्णों की संख्या, जिसके बाद अंतिम वर्ण आता है।
- यदि हमें कोई संघर्ष मिलता है और एक से अधिक शब्द समान संक्षिप्तीकरण साझा करते हैं, तो केवल पहले वर्ण के बजाय एक लंबा उपसर्ग तब तक उपयोग किया जा सकता है जब तक कि शब्द से संक्षिप्तीकरण का मानचित्र अद्वितीय न हो जाए।
- जब संक्षिप्तीकरण शब्द को छोटा नहीं बनाता है, तो इसे मूल रूप में ही रखें।
इसलिए, यदि इनपुट ["like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"] जैसा है, तो आउटपुट होगा:
["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
- एक नोड संरचना परिभाषित करें, जिसमें
cntऔर 26 चाइल्ड नोड्स की एक सरणी हो, प्रारंभ में सभी खाली हों। - एक फ़ंक्शन
freeNode()परिभाषित करें, जोheadलेगा,- यदि
headnull है, तो वापस लौटें i := 0से25तक लूप चलाएं:freeNode(head के child[i])
headको डिलीट करें
- यदि
- एक फ़ंक्शन
insertNode()परिभाषित करें, जोnode, sलेगा,curr = nodei := 0सेs का आकार - 1तक लूप चलाएं:x := s[i]- यदि
node के child[x - 'a']null नहीं है, तो:node के child[x - 'a'] := एक नया नोड
node := node के child[x - 'a']node के cnt को 1 से बढ़ाएं
- एक फ़ंक्शन
abbreviate()परिभाषित करें, जोnode, sलेगा,ret := खाली स्ट्रिंगcurr = nodei := 0सेs का आकार - 1तक लूप चलाएं:x := s[i]curr := curr के child[x - 'a']- यदि
curr का cnt == 1है, तो:rem := s का आकार - (i + 2)ret := (यदि rem <= 1, तो s, अन्यथा s का सबस्ट्रिंग इंडेक्स 0 से i तक + rem को स्ट्रिंग में + s का अंतिम तत्व)- लूप से बाहर निकलें
retवापस करें
- एक फ़ंक्शन
wordsAbbreviation()परिभाषित करें, जो एक सरणीdictलेगा,n := dict का आकार- आकार
nकी एक सरणीretपरिभाषित करें - एक मैप
mपरिभाषित करें i := 0सेn-1तक लूप चलाएं:word := dict[i]rem := word का आकार - 2x := (यदि rem <= 1, तो word, अन्यथा word का पहला तत्व + rem + word का अंतिम तत्व)m[x] के अंत में i डालेंret[i] := x
- मैप
mमें प्रत्येक कुंजी-मान जोड़ीitके लिए:- यदि
it के मान का आकार <= 1है, तो:it को बढ़ाएं- अगले पुनरावृत्ति पर जाएं
head := एक नया नोडi := 0सेit के मान का आकार - 1तक लूप चलाएं:idx := it के मान[i]insertNode(head, dict[idx])
i := 0सेit के मान का आकार - 1तक लूप चलाएं:idx := it के मान[i]ret[idx] := abbreviate(head, dict[idx])
freeNode(head)it को बढ़ाएं
- यदि
retवापस करें
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
उदाहरण
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
struct Node{
int cnt;
Node* child[26];
Node(){
cnt = 0;
for(int i = 0; i < 26; i++)child[i] = NULL;
}
};
class Solution {
public:
void freeNode(Node* head){
if (!head)
return;
for (int i = 0; i < 26; i++) {
freeNode(head->child[i]);
}
delete head;
}
void insertNode(Node* node, string s){
Node* curr = node;
for (int i = 0; i < s.size(); i++) {
char x = s[i];
if (!node->child[x - 'a']) {
node->child[x - 'a'] = new Node();
}
node = node->child[x - 'a'];
node->cnt++;
}
}
string abbreviate(Node* node, string s){
string ret = "";
Node* curr = node;
for (int i = 0; i < s.size(); i++) {
char x = s[i];
curr = curr->child[x - 'a'];
if (curr->cnt == 1) {
int rem = s.size() - (i + 2);
ret = rem <= 1 ? s : s.substr(0, i + 1) + to_string(rem) + s.back();
break;
}
}
return ret;
}
vector<string> wordsAbbreviation(vector<string>& dict) {
int n = dict.size();
vector<string> ret(n);
map<string, vector<int> > m;
for (int i = 0; i < n; i++) {
string word = dict[i];
int rem = word.size() - 2;
string x = rem <= 1 ? word : word.front() + to_string(rem) + word.back();
m[x].push_back(i);
ret[i] = x;
}
Node* head;
map<string, vector<int> >::iterator it = m.begin();
while (it != m.end()) {
if (it->second.size() <= 1) {
it++;
continue;
}
head = new Node();
for (int i = 0; i < it->second.size(); i++) {
int idx = it->second[i];
insertNode(head, dict[idx]);
}
for (int i = 0; i < it->second.size(); i++) {
int idx = it->second[i];
ret[idx] = abbreviate(head, dict[idx]);
}
freeNode(head);
it++;
}
return ret;
}
};
int main(){
Solution ob;
vector<string> v =
{"like","god","internal","me","internet","interval","intension","face","intrusion"};
print_vector(ob.wordsAbbreviation(v));
}
इनपुट
{"like","god","internal","me","internet","interval","intension","face","intrusion"}
आउटपुट
[l2e, god, internal, me, i6t, interval, inte4n, f2e, intr4n, ]