C++で各パズルに対する有効な単語の数を求める方法

問題の概要

パズル文字列が与えられたとき、ある単語が「有効」であるためには、次の2つの条件を満たす必要があります。

• 単語がパズルの先頭の文字を含んでいること
• 単語を構成するすべての文字が、パズルにも含まれていること

たとえば、パズルが「abcdefg」である場合、「face」や「cabbage」は有効な単語です。一方、「beefed」は「a」を含まないため無効であり、「based」はパズルに存在しない「s」を含むため無効となります。

ここでの課題は、答えのリスト answers を求めることです。answers[i] は、単語リスト words の中で、パズル puzzles[i] に対して有効となる単語の個数を表します。

入力例と出力例

たとえば、入力が次のとおりだとします。

words = ["aaaa", "asas", "able", "ability", "actt", "actor", "access"]
puzzles = ["aboveyz", "abrodyz", "abslute", "absoryz", "actresz", "gaswxyz"]

この場合の出力は [1, 1, 3, 2, 4, 0] になります。その内訳は以下のとおりです。

• "aboveyz" → 有効な単語は「aaaa」の 1 個
• "abrodyz" → 有効な単語は「aaaa」の 1 個
• "abslute" → 有効な単語は「aaaa」「asas」「able」の 3 個
• "absoryz" → 有効な単語は「aaaa」「asas」の 2 個
• "actresz" → 有効な単語は「aaaa」「asas」「actt」「access」の 4 個
• "gaswxyz" → 0 個（リスト内のどの単語も「g」を含まないため）

解決の考え方：ビットマスクの活用

この問題は、各単語・各パズルを 26 ビットの整数（ビットマスク）に変換して扱うことで、効率的に解けます。アルファベットの各文字を 1 ビットに対応させ、その文字が含まれていれば該当ビットを立てるイメージです。

アルゴリズムの手順

1. getMask() 関数を定義する：文字列 s を受け取り、mask = 0 から始めて、s の各文字 c について mask |= 2^(c - 'a') を計算し、最後に mask を返します。
2. 単語側の前処理：各単語 w[i] のマスクを計算し、map m に「マスク値 → そのマスクを持つ単語の個数」として記録します。同じ文字セットを持つ単語をまとめて数えられるのがポイントです。
3. パズル側の処理：各パズル p[i] について、パズル全体のマスク mask と、先頭文字に対応するビット first = 2^(word[0] - 'a') を求めます。
4. 部分集合の列挙：current = mask から始め、current = (current - 1) & mask を繰り返すことで、mask のすべての部分集合を列挙できます。
5. カウント：各部分集合 current が先頭文字のビット first を含む場合、m[current] を答えに加算します。これが「先頭文字を含み、かつ使用文字がパズル内に収まる単語」の総数になります。

部分集合列挙のテクニック sub = (sub - 1) & mask はビット演算の定番手法で、マスクが表す文字の組み合わせすべてを素早く走査できます。全単語と全パズルを総当たりで比較するよりも大幅に計算量を抑えられる点が、このアプローチの大きな利点です。

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|= 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]