ソース:プログラマ

質問する

開発チーム内で開発活動を担当していた「無知」は、最近行われたカカの表情活動で異常な方法で当選しようとした応募者を発見した.これらの応募者を収集し、不良ユーザーの名義でリストをリストし、当選者代表の「専門家」に転送し、当選処理時に排除します.プライバシーを保護するために、ユーザーの特定のIDを「*」文字で隠し、送信します.1文字に「*」文字が使用され、各IDには少なくとも1文字が使用されます.
「無知」と「専門家」は、不良ユーザーのリストに映った応募者IDを題材IDと呼ぶことにした.
たとえば、イベントに対して次の完全なユーザーIDリストが指定されている場合:
応募者ID
frodo, fradi, crodo, abc123, frodoc
不良ユーザーIDリストがある場合は、次の操作を行います.
不良ユーザー
fr*d*, abc1**
次の2つの場合、不良ユーザーにマッピングし、当選から除外するトピックIDリストが必要になる場合があります.
[frodo, abc123], [fradi, abc123]
アクティブ応募者IDリスト付きの配列user idと不良ユーザIDリストを含む配列無効idをパラメータとする場合、solution関数を完了し、当選中の題材IDリストを除外するためにいくつかの場合に発生する可能性のある数を返します.
せいげんじょうけん

user id配列のサイズは8を超えない.

user id配列の各要素の値は、1または8未満の長さの文字列です.

登録ユーザーのIDは重複しません.

のユーザIDは、小文字と数字で構成される.

で無効になっているid配列のサイズはuser id配列のサイズ以下です.

で無効になっているid配列の各要素の値は、1または8未満の長さの文字列です.

不良ユーザIDには、アルファベット小文字、数字、およびマスキング用文字「*」のみが含まれます.

不良ユーザIDには、1つ以上の"*"文字が含まれています.

不良ユーザIDは1つの応募者IDに相当し、同じ応募者IDが重複し、*トピックIDリストには入らない.

トピックのIDリストを取得した場合、これらのIDの順序にかかわらず、IDリストの内容が同じであれば、それを同一と見なし、一括して計算することができる.

問題を解く

user idと無効idから1つずつ抽出します.

user idのモードが無効idと一致する場合、ban idにidが追加される.

で選択されたIDを除いて、論理を繰り返す.

さらに

の「禁止id」を引かなければ、これまで引いた「禁止id」の組み合わせを追加します.

は、すべての組合せを返します.

この組合せの各値を並べ替えた後、重ならない総文字列の個数を求める.

インプリメンテーションコード

const match = (id, pattern) => RegExp(`^${pattern.replace(/\*/g, ".")}$`).test(id);
const pick = (arr, i) => [...arr.slice(0,i),...arr.slice(i+1)];

const dfs = (user_id, banned_id, ban, arr) => {
    if(banned_id.length === 0)arr.push(ban);
    else{
        for(let i = 0, repeat=user_id.length; i < repeat; ++i){
            if (match(user_id[i], banned_id[0])) {
                dfs(pick(user_id, i), pick(banned_id, 0), [...ban, user_id[i]], arr);
            }
        }
    }
    return arr;
}

const solution = (user_id, banned_id) => 
new Set(dfs(user_id, banned_id, [], []).map(v => v.sort().join())).size;