C++の各パズルの有効な単語の数

パズルの文字列があるとすると、次の両方の条件が有効な場合、単語は有効です-

• 単語にはパズルの最初の文字が含まれています。

• 単語の各文字について、その文字はパズルの中にあります。

パズルが「abcdefg」のようなものである場合、有効な単語は「顔」、「キャベツ」などであるという例を考えてみましょう。ただし、一部の無効な単語は、「a」がないため「強化」され、パズルに存在しない「s」があるため「ベース」になります。

答えのリストを見つける必要があります。ここで、answer [i]は、パズルパズル[i]に関して有効な特定の単語リストの単語の数です。

したがって、入力がwords =["aaaa"、 "asas"、 "able"、 "ability"、 "actt"、 "actor"、 "access"]の場合、puzzles =["aboveyz"、 "abrodyz"、 "abslute"、 "absoryz"、 "actresz"、 "gaswxyz"]の場合、出力は[1,1,3,2,4,0]になり、 "aboveyz"の有効な単語の1つとして： "aaaa"、one 「abrodyz」の有効な単語：「aaaa」、「abslute」の3つの有効な単語：「aaaa」、「asas」、「able」、「absoryz」の2つの有効な単語：「aaaa」、「asas」、4つの有効な単語「actresz」の場合：「aaaa」、「asas」、「actt」、「access」であり、「gaswxyz」の有効な単語がないため、リスト内のどの単語にも文字「g」が含まれていません。

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

• 関数getMask（）を定義します。これにはsがかかります

• マスク：=0

• 初期化i：=0の場合、i

  • mask：=mask OR 2 ^（s [i]-'a'のASCII）

• リターンマスク

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

• 配列を定義します

• 1つのマップを定義するm

• 初期化i：=0の場合、i

  • 単語：=w [i]

  • マスク：=0

  • 初期化j：=0の場合、j <ワードのサイズの場合、更新（jを1増やします）、do-

    • mask：=mask OR getMask（w [i]）

  • （m [マスク]を1増やします）

• 初期化i：=0の場合、i

  • 単語：=p [i]

  • マスク：=getMask（word）

  • 最初：=2 ^（word [0]-'a'のASCII）

  • 現在：=マスク

  • temp：=0

  • 現在>0の場合、実行-

    • current＆firstがゼロ以外の場合、-

      • current：=（current-1）AND mask

  • ansの最後にtempを挿入します

• ansを返す

理解を深めるために、次の実装を見てみましょう-

例

#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;
}
typedef long long int lli;
class Solution {
   public:
   lli getMask(string s){
      lli mask = 0;
      for(int i =0;i<s.size();i++){
         mask|= 1<<(s[i]-'a');
      }
      return mask;
   }
   vector<int> findNumOfValidWords(vector<string>& w, vector<string>& p) {
      vector <int> ans;
      map <lli, lli > m;
      for(int i =0;i<w.size();i++){
         string word = w[i];
         lli mask = 0;
         for(int j =0;j<word.size();j++){
            mask|= getMask(w[i]);
         }
         m[mask]++;
      }
      for(int i = 0; i<p.size();i++){
         string word = p[i];
         lli mask = getMask(word);
         lli first = 1<<(word[0]-'a');
         lli current = mask;
         lli temp = 0;
         while(current>0){
            if(current & first)temp+=m[current];
            current = (current-1)&mask;
         }
         ans.push_back(temp);
      }
      return ans;
   }
};
main(){
   Solution ob;
   vector<string> v = {"aaaa","asas","able","ability","actt","actor","access"};
   vector<string> v1 = {"aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"};
   print_vector(ob.findNumOfValidWords(v,v1));
}

入力

{"aaaa","asas","able","ability","actt","actor","access"},
{"aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"}

出力

[1, 1, 3, 2, 4, 0, ]