मान लीजिए हमारे पास "word" जैसी एक स्ट्रिंग है जिसमें निम्नलिखित संक्षिप्तीकरण हैं: ["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]। हमारे पास एक लक्ष्य स्ट्रिंग और एक डिक्शनरी में स्ट्रिंग्स का सेट भी है, हमें इस लक्ष्य स्ट्रिंग का एक संक्षिप्तीकरण ढूंढना है जिसमें सबसे छोटी संभव लंबाई हो जैसे कि यह डिक्शनरी में स्ट्रिंग्स के संक्षिप्तीकरणों के साथ संघर्ष न करे। यहां संक्षिप्तीकरण में प्रत्येक संख्या या अक्षर को लंबाई = 1 माना जाता है। तो उदाहरण के लिए, संक्षिप्तीकरण "a32bc" की लंबाई = 4 है।
तो, यदि इनपुट "apple" है, और डिक्शनरी ["blade"] है, तो आउटपुट "a4" होगा
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
एक ऐरे dict परिभाषित करें
abbrLen() नामक एक फ़ंक्शन परिभाषित करें, जो mask लेगा,
ret := n
b := 3 से आरंभ करें, जब b < bn, अद्यतन करें b <<= 1, करें −
यदि (mask AND b) 0 के समान है, तो −
(ret को 1 से घटाएं)
ret लौटाएं
dfs() नामक एक फ़ंक्शन परिभाषित करें, जो bit, mask लेगा,
len := abbrLen(mask)
यदि len >= minLen, तो −
लौटें
match := true
dict में प्रत्येक d के लिए, करें −
यदि (mask AND d) 0 के समान है, तो −
match := false
लूप से बाहर आएं
यदि match शून्येतर है, तो −
minLen := len
minab := mask
अन्यथा −
b := bit से आरंभ करें, जब b < bn, अद्यतन करें b := b*2, करें −
यदि (cand AND b) 0 के बराबर नहीं है, तो −
dfs(b*2, mask OR b)
मुख्य विधि से निम्नलिखित करें −
ret := खाली स्ट्रिंग
n := target का आकार
bn := 2^n
cand := 0
minLen := inf
डिक्शनरी में प्रत्येक s के लिए −
यदि s का आकार n के बराबर नहीं है, तो −
निम्नलिखित भाग को अनदेखा करें, अगले पुनरावृत्ति पर जाएं
word := 0
i := 0 से आरंभ करें, जब i, s के आकार से कम, अद्यतन करें (i को 1 से बढ़ाएं), करें −
यदि s[i], target[i] के बराबर नहीं है, तो −
word := word OR (2^i)
word को dict के अंत में डालें
cand := cand OR word
dfs(1, 0)
i := 0 से आरंभ करें, जब i < n, करें −
यदि (minab AND 2^i) 0 के बराबर नहीं है, तो −
ret := ret + target[i]
(i को 1 से बढ़ाएं)
अन्यथा
j := i
जब तक (i < n और (minab AND 2^i) 0 के समान है), करें −
(i को 1 से बढ़ाएं)
ret := ret को (i - j) के साथ जोड़ें
ret लौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −
#include <bits/stdc++.h> using namespace std; class Solution { public: int n, cand, bn, minLen, minab; vector<int> dict; int abbrLen(int mask) { int ret = n; for (int b = 3; b < bn; b <<= 1) { if ((mask & b) == 0) ret--; } return ret; } void dfs(int bit, int mask) { int len = abbrLen(mask); if (len >= minLen) return; bool match = true; for (int d : dict) { if ((mask & d) == 0) { match = false; break; } } if (match) { minLen = len; minab = mask; } else { for (int b = bit; b < bn; b <<= 1) { if ((cand & b) != 0) dfs(b << 1, mask | b); } } } string minAbbreviation(string target, vector<string> &dictionary) { string ret = ""; n = target.size(); bn = 1 << n; cand = 0; minLen = INT_MAX; for (string &s : dictionary) { if (s.size() != n) continue; int word = 0; for (int i = 0; i < s.size(); i++) { if (s[i] != target[i]) word |= (1 << i); } dict.push_back(word); cand |= word; } dfs(1, 0); for (int i = 0; i < n;) { if ((minab & (1 << i)) != 0) { ret += target[i]; i++; } else { int j = i; while (i < n && (minab & (1 << i)) == 0) i++; ret += to_string(i - j); } } return ret; } }; main() { Solution ob; vector<string> v = {"blade"}; cout << (ob.minAbbreviation("apple",v)); }इनपुट
"apple",{"blade"}आउटपुट
a4