मान लें हमारे पास स्ट्रिंग्स की एक सूची है जिसे शब्दकोश कहा जाता है। हमारे पास एक अन्य पैटर्न स्ट्रिंग है। हमारा कार्य उन स्ट्रिंग्स को ज्ञात करना है जो पैटर्न से मेल खाती हैं। मान लें शब्दकोश ["abb", "xyz", "aab", "kmm"] की तरह है, और पैटर्न "stt" है, तो परिणाम "abb" और "kmm" होंगे। चूंकि पैटर्न में पहले एक अक्षर है, फिर दो समान अक्षर, इसलिए यह समान पैटर्न वाली स्ट्रिंग्स का अनुसरण करेगा।
इस समस्या को हल करने के लिए, हम पैटर्न को इस तरह एन्कोड करेंगे कि शब्दकोश से कोई भी शब्द, जो पैटर्न से मेल खाता है, एन्कोडिंग के बाद पैटर्न के समान हैश होगा। हम शब्दकोश में सभी शब्दों के माध्यम से पुनरावृति करेंगे और उन्हें प्रदर्शित करेंगे जहां हैश समान है।
उदाहरण
#include <iostream>
#include <unordered_map>
#include <unordered_set>
using namespace std;
string stringEncode(string str) {
unordered_map map;
string encoded_str = "";
int i = 0;
for (char ch : str) {
if (map.find(ch) == map.end())
map[ch] = i++;
encoded_str += to_string(map[ch]);
}
return encoded_str;
}
void matchedPattern(unordered_set dict, string pattern) {
int patt_len = pattern.length();
string hash = stringEncode(pattern);
for (string word : dict) {
if (word.length() == patt_len && stringEncode(word) == hash)
cout << word << " ";
}
}
int main() {
unordered_set dict = {"abb", "xyz", "aab", "kmm"};
string pattern = "stt";
matchedPattern(dict, pattern);
}
आउटपुट
kmm abb
