พิจารณาว่าเรามีรายการสตริงที่เรียกว่าพจนานุกรม เรามีสตริงรูปแบบอื่น งานของเราคือค้นหาสตริงที่ตรงกับรูปแบบ สมมติว่าพจนานุกรมเป็นเหมือน ["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
