C++でのキャメルケースマッチング

クエリのリストとパターンがあるとすると、ブール値のリストとなる回答を返す必要があります。ここで、answer [i]は、querys[i]がパターンに一致する場合にのみtrueになります。クエリと同じになるようにパターンワードに小文字を挿入できる場合、クエリワードは特定のパターンに一致します。

したがって、入力が["FooBar"、 "FooBarTest"、 "FootBall"、 "FrameBuffer"、 "ForceFeedBack"]のようで、pattern ="FB"の場合、結果は[true、false、true、false、false]になります。 。

これを解決するには、次の手順に従います-

• insertNode（）というメソッドを定義します。これには、ヘッドと文字列が必要です

• curr：=ヘッド

• 0からsのサイズまでの範囲のiの場合– 1

  • x：=s [i]

  • currのchild[x]がnullでない場合、currのchild [x]：=new node

  • curr：=currの子[x]

• set isEnd of curr：=true

• メインの方法から、次のようにします-

• head：=新しいノード、headにパターンを挿入、n：=クエリ配列のサイズ、m：=tempのサイズ、ok：=true

• 0からm–1の範囲のjの場合

  • x：=temp [j]

  • currのchild[x]の場合、curr：=currのchild[x]

  • それ以外の場合、temp [j]がAからZの範囲にある場合は、ok：=falseで、ループから解除します

  • ans [i]：=isEnd of curr AND 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, ]