Số lượng từ hợp lệ cho mỗi câu đố trong C ++

Giả sử có một chuỗi câu đố, một từ hợp lệ nếu cả hai điều kiện sau hợp lệ -

• từ chứa chữ cái đầu tiên của câu đố.

• Đối với mỗi chữ cái trong từ, chữ cái đó nằm trong câu đố.

Giả sử nếu chúng ta xem xét một ví dụ rằng, nếu câu đố giống như "abcdefg", thì các từ hợp lệ là "khuôn mặt", "bắp cải", v.v.; nhưng một số từ không hợp lệ được "củng cố" vì không có "a" và "dựa" vì có "s" không có trong câu đố.

Chúng ta phải tìm danh sách các câu trả lời, trong đó đáp án [i] là số từ trong các từ trong danh sách từ đã cho có giá trị đối với các câu đố câu đố [i].

Vì vậy, nếu đầu vào là words =["aaaa", "asas", "could", "ability", "actt", "Actor", "access"], puzzle =["aboveyz", "abrodyz", "abslute", "absoryz", "actresz", "gaswxyz"], thì đầu ra sẽ là [1,1,3,2,4,0], là một từ hợp lệ cho "trênyz":"aaaa", một từ hợp lệ cho "abrodyz":"aaaa", ba từ hợp lệ cho "abslute":"aaaa", "asas", "could", hai từ hợp lệ cho "absoryz":"aaaa", "asas", bốn từ hợp lệ đối với "actresz":"aaaa", "asas", "actt", "access" và không có từ nào hợp lệ cho "gaswxyz" vì không có từ nào trong danh sách chứa ký tự 'g'.

Để 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 hàm getMask (), điều này sẽ mất s,

• mặt nạ:=0

• để khởi tạo i:=0, khi i

  • mask:=mask OR 2 ^ (s [i] - ASCII của 'a')

• mặt nạ trả lại

• Từ phương thức chính, hãy làm như sau -

• Xác định ans mảng

• Xác định một bản đồ m

• để khởi tạo i:=0, khi i

  • từ:=w [i]

  • mặt nạ:=0

  • để khởi tạo j:=0, khi j

    • mask:=mask HOẶC getMask (w [i])

  • (tăng m [mask] lên 1)

• để khởi tạo i:=0, khi i

  • từ:=p [i]

  • mask:=getMask (word)

  • đầu tiên:=2 ^ (từ [0] - ASCII của 'a')

  • hiện tại:=mask

  • tạm thời:=0

  • trong khi hiện tại> 0, làm -

    • nếu hiện tại &đầu tiên là khác 0, thì -

      • current:=(current - 1) AND mask

  • chèn tạm thời vào cuối ans

• trả lại ans

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

Ví dụ

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

Đầu vào

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

Đầu ra

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