C++ এ ক্যামেলকেস ম্যাচিং

ধরুন আমাদের কাছে প্রশ্নগুলির একটি তালিকা এবং একটি প্যাটার্ন রয়েছে, আমাদের একটি উত্তর দিতে হবে যা হবে বুলিয়ানের তালিকা, যেখানে উত্তর[i] সত্য হয় এবং শুধুমাত্র যদি প্রশ্নগুলি[i] প্যাটার্নের সাথে মেলে। একটি ক্যোয়ারী শব্দ একটি প্রদত্ত প্যাটার্নের সাথে মেলে যখন আমরা প্যাটার্ন শব্দে ছোট হাতের অক্ষর সন্নিবেশ করতে পারি যাতে এটি কোয়েরির সমান হয়৷

সুতরাং ইনপুট যদি ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"] এবং প্যাটার্ন ="FB" এর মত হয়, তাহলে ফলাফল হবে [সত্য, মিথ্যা, সত্য, মিথ্যা, মিথ্যা] .

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• insertNode() নামক একটি পদ্ধতি সংজ্ঞায়িত করুন, এটি মাথা এবং স্ট্রিং s

  নেয়

• curr :=মাথা

• 0 থেকে s - 1

  এর আকারের মধ্যে i এর জন্য

  • x :=s[i]

  • যদি curr এর চাইল্ড[x] শূন্য না হয়, তাহলে curr এর চাইল্ড[x] :=নতুন নোড

  • curr :=curr এর সন্তান [x]

• সেট isEnd of curr :=true

• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -

• head :=নতুন নোড, মাথায় প্যাটার্ন ঢোকান, n :=ক্যোয়ারী অ্যারের আকার, m :=তাপমাত্রার আকার, ঠিক আছে :=সত্য

• j-এর জন্য 0 থেকে m – 1

  পরিসরে

  • x :=তাপমাত্রা[j]

  • যদি curr এর সন্তান [x], তাহলে curr :=curr এর সন্তান [x]

  • অন্যথায় যখন temp[j] A থেকে Z রেঞ্জে থাকে, তখন ঠিক আছে :=মিথ্যা এবং ব্রেক ফ্রম লুপ

  • উত্তর[i] :=curr এর শেষ এবং ঠিক আছে

• উত্তর ফেরত দিন

উদাহরণ(C++)

আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
struct Node{
   bool isEnd;
   map <char, Node*> child;
   Node(){
      isEnd = false;
   }
};
class Solution {
   public:
   void insertNode(Node* head, string s){
      Node* curr = head;
      for(int i = 0; i < s.size(); i++){
         char x = s[i];
         if(!curr->child[x]){
            curr->child[x] = new Node();
         }
         curr = curr->child[x];
      }
      curr->isEnd = true;
   }
   vector<bool> camelMatch(vector<string>& queries, string pattern){
      Node* head = new Node();
      insertNode(head, pattern);
      int n = queries.size();
      vector <bool> ans(n);
      Node* curr;
      bool ok;
      for(int i = 0; i < n; i++){
         string temp = queries[i];
         curr = head;
         int m = temp.size();
         ok = true;
         for(int j = 0; j < m; j++){
            char x = temp[j];
            if(curr->child[x]){
               curr = curr->child[x];
            }
            else if(temp[j] >= 'A' && temp[j] <= 'Z'){
               ok = false;
               break;
            }
         }
         ans[i] = curr->isEnd && ok;
      }
      return ans;
   }
};
main(){
   vector<string> v1 = {"FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"};
   Solution ob;
   print_vector(ob.camelMatch(v1, "FB"));
}

ইনপুট

["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"]
"FB"

আউটপুট

[1, 0, 1, 1, 0, ]