JavaScriptでランダムな文字列を使って配列内の名前を形成できるか判定する方法

JavaScriptでは、文字列の各文字の出現回数を数えることで、ある文字列が別の文字列の組み合わせで作れるかどうかを効率的に判定できます。本記事では、配列に含まれる名前の中から、指定されたランダムな文字列だけで完全に構成できる要素を見つけ出す関数の実装方法を解説します。

問題の概要

まず、次のような名前を格納した文字列の配列があるとします。

const arr = ['Dinesh', 'Mahesh', 'Rohit', 'Kamal', 'Jatin Sapru', 'Jai'];

そして、ランダムな文字の集まりからなる文字列が1つ与えられます。

const str = 'lsoaakjm';

ここで求められるのは、この配列と文字列を2つの引数として受け取るJavaScript関数を作成することです。

関数は、配列の各要素について、その要素が第2引数として渡された文字列だけを使って完全に形成できるかどうかを確認する必要があります。同じ文字は文字列内の出現回数までしか使えない点に注意してください。

この条件を満たす要素が配列内に存在すればその要素を返し、存在しなければ空文字列を返します。

実装の考え方

判定には「文字カウントマップ（ハッシュマップ）」を利用します。手順は以下の通りです。

1. 対象の名前を小文字に変換して比較できるようにする。
2. ランダム文字列の各文字の出現回数をマップに記録する。
3. 名前の各文字について、マップに残りがあれば消費し、なければその時点で不成立と判断する。
4. すべての文字を消費できた場合のみ、その名前が形成可能とみなす。

サンプルコード

const arr = ['Dinesh', 'Mahesh', 'Rohit', 'Kamal', 'Jatin Sapru', 'Jai'];
const str = 'lsoaakjm';

// 文字列の各文字の出現回数をマップに記録する
const initialise = (str = '', map) => {
    for(let i = 0; i < str.length; i++){
        map[str[i]] = (map[str[i]] || 0) + 1;
    };
};

// マップを空にして再利用できるようにする
const deleteAll = map => {
    for(key in map){
        delete map[key];
    };
};

// 配列の中から文字列だけで形成できる名前を探す
const checkForFormation = (arr = [], str = '') => {
    const map = {};
    for(let i = 0; i < arr.length; i++){
        const el = arr[i].toLowerCase();
        initialise(str, map);
        let j;
        for(j = 0; j < el.length; j++){
            const char = el[j];
            if(!map[char]){
                break;
            }else{
                map[char]--;
            }
        };
        if(j === el.length){
            return arr[i];
        };
        deleteAll(map);
    }
    return '';
};
console.log(checkForFormation(arr, str));

出力結果

コンソールへの出力は以下のようになります。

Kamal

コードの解説

initialise 関数は、ランダム文字列 'lsoaakjm' の各文字（l:1、s:1、o:1、a:2、k:1、j:1、m:1）をキーに出現回数として記録します。

checkForFormation 関数は、配列の各名前を順番に調べます。例えば「Dinesh」には d や n、e などが含まれていますが、これらはランダム文字列に存在しないため即座に不合格となります。一方「Kamal」は k・a・m・a・l の5文字すべてがランダム文字列内で賄えるため、最初に条件を満たした要素として返されます。

どの名前も形成できない場合は、関数は最後に空文字列 '' を返します。

補足：パフォーマンスに関する注意

上記のコードでは各要素ごとにマップを初期化していますが、より効率化したい場合は、ランダム文字列のカウントマップをループの外で一度だけ作成しておき、各名前の判定時にコピーを使う方法もあります。また、大文字・小文字を区別したい場合は toLowerCase() の呼び出しを削除してください。