C ++中的驼峰匹配

假设我们有一个查询列表和一个模式，我们必须返回一个将是布尔值列表的答案，其中且仅当query [i]与该模式匹配时，答案[i]为真。当我们可以在模式词中插入小写字母以使其等于查询时，查询词会匹配给定的模式。

因此，如果输入类似于[“ FooBar”，“ FooBarTest”，“ FootBall”，“ FrameBuffer”，“ ForceFeedBack”]和pattern =“ FB”，则结果将为[true，false，true，false，false] 。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个名为的方法insertNode()，该方法需要head和string

• curr：=头

• 当我的范围是0到s的大小– 1

• x：= s [i]

• 如果curr的child [x]不为null，则curr的child [x]：=新节点

• curr：= curr的子级[x]

• 设置isEnd of curr：= true

• 从主要方法中，执行以下操作-

• head：=新节点，将模式插入head，n：=查询数组的大小，m：=临时大小，确定：= true

• 对于j，范围从0到m – 1

• x：=温度[j]

• 如果curr的child [x]，则curr：= curr的child [x]

• 否则，当temp [j]在A到Z的范围内时，则ok：= false并从循环中断

• ans [i]：= isEnd curr和OK

• 返回ans

例子（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, ]