JavaScriptで文字列から形成できる最長の単語を見つける方法

問題

JavaScriptで関数を記述する必要があります。この関数は、第1引数としてランダムな英字からなる文字列 str を、第2引数として文字列の配列 arr を受け取ります。

関数の役割は、文字列 str からいくつかの文字を削除したときに、配列 arr にも存在する最長の単語を作れるかどうかを調べることです。そして、作成可能な最長の文字列を返します。

該当する文字列が存在しない場合は、空文字列を返す必要があります。

例えば、関数への入力が以下の場合を考えてみましょう。

const str = 'sdgfdfghdjh';
const arr = ['sdf', 'fghj', 'gfdfg', 'absc', 'a', 'hasl'];

この場合の出力は以下のようになります。

const output = 'gfdfg';

出力の解説

配列の1番目と2番目の要素（'sdf' と 'fghj'）も、文字列から文字を削除することで作成可能です。しかし 'gfdfg' は5文字と最も長いため、これが正解となります。

実装例

この問題を解くコードは以下の通りです。

const str = 'sdgfdfghdjh';
const arr = ['sdf', 'fghj', 'gfdfg', 'absc', 'a', 'hasl'];

const findLongestWord = (str = '', arr = []) => {
    arr.sort((a, b) => {
        if (a.length !== b.length) {
            return b.length - a.length;
        };
        return a.localeCompare(b);
    });
    for(const word of arr){
        let index = -1;
        for(const char of word){
            index = str.indexOf(char, index + 1);
            if(index < 0){
                break;
            };
        };
        if (index >= 0){
            return word;
        };
    };
    return '';
};
console.log(findLongestWord(str, arr));

コードの解説

このコードでは、以下の手順で処理を行っています。

• まず、配列 arr を「文字数が多い順」にソートし、同じ長さの場合は localeCompare による辞書順（アルファベット順）で並べ替えます。

• 次に、配列内の各単語についてループ処理を行います。単語の各文字が、indexOf の第2引数を使って前回の位置以降から順に検索され、文字列 str 内に順序どおり存在するかを確認します。1つでも見つからない文字があれば、その単語は作成不可能としてループを抜けます。

• すべての文字が順序どおりに見つかった場合のみ、その単語を答えとして返します。

辞書となる配列を事前にソートしているため、最初に条件を満たした単語が必ず最長の答えになると保証できます。これは「部分列（サブシーケンス）」の判定を効率的に行う定番テクニックです。

出力結果

コンソールには以下のように出力されます。

gfdfg