Tìm tất cả các chuỗi khớp với mẫu cụ thể trong từ điển bằng C ++

Hãy xem xét chúng ta có một danh sách các chuỗi được gọi là từ điển. Chúng tôi có một chuỗi mẫu khác. Nhiệm vụ của chúng ta là tìm những chuỗi phù hợp với mẫu. Giả sử từ điển giống như [“abb”, “xyz”, “aab”, “kmm”] và mẫu là “stt”, thì kết quả sẽ là “abb” và “kmm”. Vì lúc đầu mẫu có một chữ cái, sau đó là hai chữ cái giống nhau, nên nó sẽ tuân theo các chuỗi mẫu giống nhau.

Để giải quyết vấn đề này, chúng tôi sẽ mã hóa mẫu theo cách sao cho bất kỳ từ nào từ từ điển, khớp với mẫu, sẽ có cùng một hàm băm giống như mẫu sau khi mã hóa. Chúng tôi sẽ lặp lại tất cả các từ trong từ điển và hiển thị chúng ở những nơi có hàm băm giống nhau.

Ví dụ

#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);
}

Đầu ra

kmm abb