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

คำอธิบายโจทย์

คำถูกต้องต่อ puzzle ถ้า: 1) มีตัวอักษรแรกของ puzzle 2) ทุกตัวอักษรในคำอยู่ใน puzzle หาจำนวนคำถูกต้องสำหรับแต่ละ puzzle

ตัวอย่าง

words = ["aaaa","asas","able","ability","actt","actor","access"]

puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]

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

วิธีแก้ปัญหา

Bitmask + Subset Enumeration:

1. แปลงแต่ละ word เป็น bitmask 26 bits นับความถี่ใน map
2. สำหรับแต่ละ puzzle: สร้าง mask, first_bit = puzzle[0]
3. วนทุก subset ของ puzzle mask: sub = (sub-1) & mask
4. ถ้า sub มี first_bit → บวก m[sub] เข้าไป

Time: O(W×L + P×2^7) เนื่องจาก puzzle มี 7 ตัวอักษร

การทำงานของโค้ด

#include <bits/stdc++.h>
using namespace std;
typedef long long lli;

class Solution {
public:
    lli getMask(string s) {
        lli mask = 0;
        for(char c : s) mask |= 1LL << (c-'a');
        return mask;
    }
    
    vector<int> findNumOfValidWords(vector<string>& w, vector<string>& p) {
        vector<int> ans;
        unordered_map<lli, int> m;
        
        for(string& word : w) {
            lli mask = getMask(word);
            m[mask]++;
        }
        
        for(string& word : p) {
            lli mask = getMask(word);
            lli first = 1LL << (word[0]-'a');
            int cnt = 0;
            for(lli sub = mask; sub; sub = (sub-1) & mask) {
                if(sub & first) cnt += m[sub];
            }
            ans.push_back(cnt);
        }
        return ans;
    }
};

int main() {
    Solution ob;
    vector<string> v = {"aaaa","asas","able","ability","actt","actor","access"};
    vector<string> v1 = {"aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"};
    auto res = ob.findNumOfValidWords(v, v1);
    for(int x : res) cout << x << " ";
    return 0;
}

อินพุต

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

เอาต์พุต

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