Khớp Camelcase trong C ++

Giả sử chúng ta có một danh sách các truy vấn và một mẫu, chúng ta phải trả về một câu trả lời sẽ là danh sách các boolean, trong đó câu trả lời [i] là đúng nếu và chỉ khi các truy vấn [i] khớp với mẫu. Một từ truy vấn khớp với một mẫu nhất định khi chúng ta có thể chèn các chữ cái viết thường vào từ mẫu để từ đó bằng với truy vấn.

Vì vậy, nếu đầu vào là ["FooBar", "FooBarTest", "FootBall", "FrameBuffer", "ForceFeedBack"] và pattern ="FB", thì kết quả sẽ là [true, false, true, false, false] .

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một phương thức được gọi là insertNode (), phương thức này nhận head và string s

• curr:=đầu

• cho tôi trong phạm vi từ 0 đến kích thước của s-1

  • x:=s [i]

  • nếu con [x] của curr không phải là null, thì con [x] của curr:=nút mới

  • curr:=child [x] of curr

• set isEnd of curr:=true

• Từ phương thức chính, thực hiện như sau -

• head:=nút mới, chèn mẫu vào đầu, n:=kích thước của mảng truy vấn, m:=kích thước của tạm thời, ok:=true

• cho j trong phạm vi 0 đến m - 1

  • x:=temp [j]

  • if child [x] of curr, then curr:=child [x] of curr

  • ngược lại khi temp [j] nằm trong khoảng A đến Z, thì ok:=false và break fromloop

  • ans [i]:=isEnd of curr VÀ ok

• trả lại ans

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

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

Đầu ra

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