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

Cho danh sách từ words và câu đố puzzles. Từ hợp lệ nếu: chứa chữ cái đầu của puzzle, và mọi chữ cái trong từ đều có trong puzzle. Tìm số từ hợp lệ cho mỗi puzzle.

Ví dụ: words=["aaaa","asas","able","ability","actt","actor","access"], puzzles=["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"] → [1,1,3,2,4,0].

Giải pháp

Sử dụng bitmask (26 bit cho a-z) và duyệt tập con:

• Hàm getMask(s): bitmask của chuỗi s
• Đếm tần suất mask của từng từ trong words → map m
• Với mỗi puzzle:
  • mask_puzzle = getMask(puzzle)
  • first_bit = 1 << (puzzle[0]-'a')
  • Duyệt tất cả tập con của mask_puzzle: current = (current-1) & mask_puzzle
  • Nếu current & first_bit: cộng m[current] vào kết quả
• Độ phức tạp: O(|words| * L + |puzzles| * 2^7) rất nhanh

Ví dụ mã 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; 
} 

typedef long long int lli; 

class Solution { 
public: 
    lli getMask(string s) { 
        lli mask = 0; 
        for(int i = 0; i < s.size(); i++) 
            mask |= 1LL << (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 = 1LL << (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; 
    } 
}; 

int 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)); 
    return 0; 
}

Đầu vào

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

Đầu ra

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