จำนวนคำที่ถูกต้องสำหรับแต่ละปริศนาใน C++

สมมติว่ามีสตริงปริศนา คำหนึ่งถูกต้องหากทั้งสองเงื่อนไขต่อไปนี้ถูกต้อง -

• คำมีอักษรตัวแรกของปริศนา

• สำหรับแต่ละตัวอักษรในคำ ตัวอักษรนั้นอยู่ในปริศนา

สมมติว่าถ้าเราพิจารณาตัวอย่างที่ ถ้าปริศนาเป็นเหมือน "abcdefg" คำที่ถูกต้องคือ "หน้า", "กะหล่ำปลี" เป็นต้น แต่คำที่ไม่ถูกต้องบางคำ "beefed" เนื่องจากไม่มี "a" และ "based" เนื่องจากมี "s" ที่ไม่ปรากฏในปริศนา

เราต้องหารายการคำตอบ โดยที่ answer[i] คือจำนวนคำในรายการคำศัพท์ที่กำหนดซึ่งใช้ได้กับปริศนาตัวต่อ[i]

ดังนั้น หากการป้อนเป็นเหมือนคำ =["aaaa","asas","able","ability","actt","actor","access"] ปริศนา =["aboveyz","abrodyz", "abslute","absoryz","actresz","gaswxyz"] จากนั้นผลลัพธ์จะเป็น[1,1,3,2,4,0] เป็นหนึ่งคำที่ถูกต้องสำหรับ "aboveyz" :"aaaa" หนึ่งคำ คำที่ใช้ได้สำหรับ "abrodyz" :"aaaa" สามคำที่ใช้ได้สำหรับ "abslute" :"aaaa", "asas", "able", สองคำที่ใช้ได้สำหรับ "absoryz" :"aaaa", "asas", สี่คำที่ถูกต้อง สำหรับ "actresz" :"aaaa", "asas", "actt", "access" และไม่มีคำที่ถูกต้องสำหรับ "gaswxyz" ทำให้ไม่มีคำใดในรายการที่มีตัวอักษร 'g'

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน getMask() ซึ่งจะใช้เวลา s

• หน้ากาก :=0

• สำหรับการเริ่มต้น i :=0 เมื่อ i

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

• มาส์กคืน

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• กำหนดอาร์เรย์และ

• กำหนดหนึ่งแผนที่ m

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • word :=w[i]

  • หน้ากาก :=0

  • สำหรับการเริ่มต้น j :=0 เมื่อ j <ขนาดของคำ ให้อัปเดต (เพิ่ม j ขึ้น 1) ทำ−

    • หน้ากาก :=หน้ากาก OR getMask(w[i])

  • (เพิ่ม m[mask] ขึ้น 1)

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของ p ให้อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ −

  • คำ :=p[i]

  • หน้ากาก :=getMask(คำ)

  • แรก :=2^(word[0] - ASCII ของ 'a')

  • ปัจจุบัน :=หน้ากาก

  • อุณหภูมิ :=0

  • ในขณะที่ปัจจุบัน> 0 ทำ -

    • ถ้ากระแส &แรกไม่ใช่ศูนย์ แล้ว -

      • ปัจจุบัน :=(ปัจจุบัน - 1) และหน้ากาก

  • ใส่ 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, ]