JavaScriptで文字列を単語に分割できるか判定する方法

空でない文字列 str と、空でない単語のリストを格納した文字列の配列 arr が与えられます。

ここで求められているのは、str を、配列に存在する1つ以上の単語をスペースで区切った並びに分割できるかどうかを判定する関数を作成することです。

注意点

• 配列内の同じ単語は、分割の際に何度でも再利用して構いません。

• 配列には重複した単語は含まれていません。

例1

入力が次の場合を考えてみましょう。

const str = "applepenapple";
const arr = ["apple", "pen"];

このときの出力は true になります。その理由は以下の通りです。

"applepenapple" は "apple pen apple" と分割できます。

コード例

この問題を解くコードは以下のようになります。

const str = "applepenapple";
const arr = ["apple", "pen"];
const wordSequence = (str = '', arr = []) => {
    const map = {}
    function helper(str) {
        if (map.hasOwnProperty(str)) {
            return map[str]
        } else if (str=='') {
            return true
        }
        for (let i=0;i<=str.length;i++) {
            if (
                arr.includes(str.slice(i)) &&
                helper(str.slice(0, i))
            ){
                map[str] = true
                return true
            }
        };
        map[str] = false;
        return false;
    };
    return helper(str)
};
console.log(wordSequence(str, arr));

出力

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

true

コードの解説

この実装では、再帰とメモ化(キャッシュ)を組み合わせたアプローチを採用しています。

ヘルパー関数 helper は、文字列の各位置で分割を試みます。具体的には、後半部分(str.slice(i))が配列に含まれる単語と一致し、かつ前半部分(str.slice(0, i))も同様に分割可能であるかを再帰的に確認します。

オブジェクト map を使って一度計算した結果をキャッシュすることで、同じ部分文字列に対する重複した計算を回避し、処理効率を大幅に向上させています。また、空文字列に到達した場合は、すべての部分が配列内の単語へと分割できたことを意味するため、true を返します。

このように、動的計画法の考え方を取り入れることで、単純な全探索よりもはるかに高速に判定を行うことができます。