In tất cả các từ khớp với một mẫu trong Từ điển ký hiệu CamelCase trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng chuỗi trong camelcase và một mẫu. Chúng tôi phải in tất cả các chuỗi của mảng phù hợp với mẫu đã cho.

Mảng chuỗi là một mảng trong đó các phần tử thuộc kiểu dữ liệu chuỗi.

camelCase là một phương pháp phổ biến để đặt tên trong lập trình, theo cách này, chữ cái đầu tiên của từ mới bắt đầu bằng chữ hoa, còn lại tất cả đều là chữ thường.

Ví dụ - iLoveProgramming

Vấn đề - tìm tất cả các chuỗi phù hợp với một mẫu nhất định.

Ví dụ -

Input : “TutorialsPoint” , “ProgrammersPoint” , “ProgrammingLover” , “Tutorials”.
Pattern : ‘P’
Output : “TutorialsPoint” ,
“ProgrammersPoint” , “ProgrammingLover”

Giải thích - Chúng tôi đã xem xét tất cả các chuỗi có chữ ‘P’ trong đó.

Để giải quyết vấn đề này, chúng tôi sẽ thêm tất cả các khóa của từ điển vào một cây và sau đó sử dụng các ký tự viết hoa. Và xử lý các từ trong cây và in tất cả những từ phù hợp với mẫu.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
struct TreeNode{
   TreeNode* children[26];
   bool isLeaf;
   list<string> word;
};
TreeNode* getNewTreeNode(void){
   TreeNode* pNode = new TreeNode;
   if (pNode){
      pNode->isLeaf = false;
      for (int i = 0; i < 26; i++)
         pNode->children[i] = NULL;
   }
   return pNode;
}
void insert(TreeNode* root, string word){
   int index;
   TreeNode* pCrawl = root;
   for (int level = 0; level < word.length(); level++){
      if (islower(word[level]))
         continue;
      index = int(word[level]) - 'A';
      if (!pCrawl->children[index])
      pCrawl->children[index] = getNewTreeNode();
      pCrawl = pCrawl->children[index];
   }
   pCrawl->isLeaf = true;
   (pCrawl->word).push_back(word);
}
void printAllWords(TreeNode* root){
   if (root->isLeaf){
      for(string str : root->word)
         cout << str << endl;
   }
   for (int i = 0; i < 26; i++){
      TreeNode* child = root->children[i];
      if (child)
         printAllWords(child);
   }
}
bool search(TreeNode* root, string pattern){
   int index;
   TreeNode* pCrawl = root;
   for (int level = 0; level <pattern.length(); level++) {
      index = int(pattern[level]) - 'A';
      if (!pCrawl->children[index])
         return false;
      pCrawl = pCrawl->children[index];
   }
   printAllWords(pCrawl);
   return true;
}
void findAllMatch(vector<string> dictionary, string pattern){
   TreeNode* root = getNewTreeNode();
   for (string word : dictionary)
      insert(root, word);
   if (!search(root, pattern))
      cout << "No match found";
}
int main(){
   vector<string> dictionary = { "Tutorial" , "TP" , "TutorialsPoint" , "LearnersPoint", "TutorialsPointsPrograming" , "programmingTutorial"};
   string pattern = "TP";
   findAllMatch(dictionary, pattern);
   return 0;
}

Đầu ra

TP
TutorialsPoint
TutorialsPointsPrograming