การจับคู่ Camelcase ใน C ++

สมมติว่าเรามีรายการข้อความค้นหาและรูปแบบ เราต้องส่งคืนคำตอบที่จะเป็นรายการบูลีน โดยที่ answer[i] เป็นจริงก็ต่อเมื่อ query[i] ตรงกับรูปแบบเท่านั้น คำค้นหาตรงกับรูปแบบที่กำหนดเมื่อเราสามารถแทรกตัวอักษรพิมพ์เล็กลงในคำรูปแบบเพื่อให้เท่ากับข้อความค้นหา

ดังนั้นหากอินพุตเป็นเหมือน ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"] และรูปแบบ ="FB" ผลลัพธ์จะเป็น [true,false,true,false,false] .

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดวิธีการที่เรียกว่า insertNode() ซึ่งใช้ส่วนหัวและสตริง s

• curr :=หัว

• สำหรับฉันอยู่ในช่วง 0 ถึงขนาด s – 1

  • x :=s[i]

  • ถ้า child[x] ของ curr ไม่เป็นค่าว่าง ดังนั้น child[x] ของ curr :=new node

  • curr :=child[x] ของสกุลเงิน

• set isEnd of curr :=true

• จากวิธีหลัก ให้ทำดังนี้ −

• head :=โหนดใหม่ แทรกรูปแบบลงในส่วนหัว n :=ขนาดของอาร์เรย์การสืบค้น m :=ขนาดของ temp ตกลง :=true

• สำหรับ j ในช่วง 0 ถึง m – 1

  • x :=อุณหภูมิ[j]

  • ถ้า child[x] ของ curr แล้ว curr :=child[x] ของ curr

  • มิฉะนั้นเมื่อ temp[j] อยู่ในช่วง A ถึง Z ก็ ok :=false และแยกจากลูป

  • ans[i] :=isEnd of curr AND ok

• กลับมาอีกครั้ง

ตัวอย่าง(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, ]