โปรแกรม C++ หาสตริงทั้งหมดที่ตรงกับรูปแบบเฉพาะในพจนานุกรม

พิจารณาว่าเรามีรายการสตริงเรียกว่าพจนานุกรม เรามีสตริงรูปแบบอีกตัวหนึ่ง งานของเราคือหาสตริงที่ตรงกับรูปแบบ สมมติพจนานุกรมเป็น ["abb", "xyz", "aab", "kmm"] และรูปแบบคือ "stt" ผลลัพธ์จะเป็น "abb" และ "kmm" เนื่องจากรูปแบบมีตัวอักษรตัวแรก แล้วตามด้วยตัวอักษรเดียวกันสองตัว จึงจะตามรูปแบบสตริงเดียวกัน

เพื่อแก้ปัญหานี้ เราจะเข้ารหัส (encode) รูปแบบอย่างที่คำใดในพจนานุกรมที่ตรงกับรูปแบบ จะมีแฮชเหมือนกับรูปแบบหลังเข้ารหัส เราจะวนลูปทุกคำในพจนานุกรมและแสดงที่มีแฮชเหมือนกัน

ตัวอย่าง

#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