একটি স্ট্রিংয়ের লিস্ট ডিকশনারি (dictionary) হিসেবে দেওয়া থাকলে। আর একটি প্যাটার্ন স্ট্রিং দেওয়া থাকলে। প্যাটার্ন মিলে যাওয়া স্ট্রিংগুলো বের করতে হবে। ডিকশনারি ["abb", "xyz", "aab", "kmm"], প্যাটার্ন "stt" হলে ফলাফল "abb" এবং "kmm"। প্যাটার্নে প্রথমে এক অক্ষর, তারপর দুটি একই অক্ষর, তাই একই প্যাটার্নের স্ট্রিংগুলো মিলবে।
সমাধান: প্যাটার্নকে এনকোড (encode) করা যাতে ডিকশনারির যেকোনো শব্দ প্যাটার্ন মিললে, এনকোডিংয়ের পর তার হ্যাশ (hash) প্যাটার্নের হ্যাশের সমান হয়। সব শব্দ ঘুরে যেখানে হ্যাশ মিলে, সেগুলো দেখানো।
উদাহরণ
#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
