আমরা অভিধান নামক স্ট্রিং একটি তালিকা আছে বিবেচনা করুন. আমরা অন্য প্যাটার্ন স্ট্রিং আছে. আমাদের কাজ হল সেই স্ট্রিংগুলি খুঁজে বের করা যা প্যাটার্নের সাথে মেলে। ধরুন অভিধানটি হল [“abb”, “xyz”, “aab”, “kmm”], এবং প্যাটার্ন হল “stt”, তাহলে ফলাফল হবে “abb”, এবং “kmm”। যেহেতু প্যাটার্নে প্রথমে একটি অক্ষর আছে, তারপরে একই অক্ষর দুটি, তাই এটি একই প্যাটার্ন স্ট্রিং অনুসরণ করবে।
এই সমস্যাটি সমাধান করার জন্য, আমরা প্যাটার্নটিকে এমনভাবে এনকোড করব যাতে অভিধান থেকে প্যাটার্নের সাথে মেলে এমন যেকোনো শব্দ এনকোড করার পর প্যাটার্নের মতো একই হ্যাশ থাকবে। আমরা অভিধানের সমস্ত শব্দের মাধ্যমে পুনরাবৃত্তি করব এবং সেগুলিকে প্রদর্শন করব যেখানে হ্যাশ একই।
উদাহরণ
#include<iostream>
#include<unordered_map>
#include<unordered_set>
using namespace std;
string stringEncode(string str) {
unordered_map<char, int> 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<string> 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<string> dict = {"abb", "xyz", "aab", "kmm"};
string pattern = "stt";
matchedPattern(dict, pattern);
} আউটপুট
kmm abb
