JavaScriptで文字列のすべての部分文字列を再帰的に取得する方法

JavaScriptでは、文字列を引数として受け取り、その文字列から作成できるすべての部分文字列（サブストリング）を生成する関数を実装できます。本記事では、入力文字列のすべての部分文字列を配列にまとめて返す関数の作り方を、ループを使う方法と再帰を使う方法の2通りで解説します。

二重ループを使った実装

まずは、開始位置と終了位置を組み合わせる二重ループによるシンプルな実装例です。

const str = 'example';

const buildSubstrings = (str = '') => {
    let i, j;
    const res = [];
    for (i = 0; i < str.length; i++) {
        for (j = i + 1; j < str.length + 1; j++) {
            res.push(str.slice(i, j));
        };
    };
    return res;
};

console.log(buildSubstrings(str));

コードの解説

外側のループ変数 i は部分文字列の開始位置を、内側のループ変数 j は終了位置を表します。str.slice(i, j) によって、位置 i から j の直前までの文字列を切り出し、結果配列 res に追加していきます。

例えば文字列 'example' の場合、i = 0 の間に 'e'、'ex'、'exa' … と先頭から順に長さを増やした文字列が生成され、その後 i を1つずつ進めながら同様の処理を繰り返します。

出力結果

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

[
    'e', 'ex', 'exa',
    'exam', 'examp', 'exampl',
    'example', 'x', 'xa',
    'xam', 'xamp', 'xampl',
    'xample', 'a', 'am',
    'amp', 'ampl', 'ample',
    'm', 'mp', 'mpl', 'mple',
    'p', 'pl', 'ple',
    'l', 'le', 'e'
]

長さ n の文字列からは、空文字列を除いて n × (n + 1) / 2 個の部分文字列が得られます。'example' は7文字なので、7 × 8 / 2 = 28個の部分文字列が生成されていることがわかります。

再帰を使った実装

タイトルのとおり再帰処理で実装したい場合は、先頭文字から始まる部分文字列をすべて生成した後、残りの文字列に対して自分自身を呼び出す形にします。

const getSubstringsRecursive = (str = '') => {
    // 空文字列になったら再帰を終了
    if (str.length === 0) return [];

    const result = [];
    // 現在の先頭から始まる部分文字列をすべて追加
    for (let i = 1; i <= str.length; i++) {
        result.push(str.slice(0, i));
    }

    // 残りの文字列（先頭の1文字を除いたもの）で再帰呼び出し
    return result.concat(getSubstringsRecursive(str.slice(1)));
};

console.log(getSubstringsRecursive('example'));

この実装では、各再帰呼び出しのたびに文字列の先頭を1文字ずつ削りながら処理を進めるため、最終的に二重ループ版と同じ順序・同じ内容の配列が返されます。

計算量について

部分文字列の総数は n × (n + 1) / 2 個（約 O(n²) 個）あり、さらに1つずつ文字列を切り出すのに O(n) かかるため、全体の計算量は O(n³) となります。そのため、非常に長い文字列に対してこの処理を適用する場合は、パフォーマンスへの影響に注意が必要です。

まとめ

文字列のすべての部分文字列を取得するには、開始位置と終了位置の二重ループを使う方法が最も直感的です。また、再帰を用いれば「先頭からの部分文字列を生成し、残りに対して繰り返す」というシンプルな構造で同じ結果を得られます。用途に応じて、どちらのアプローチも活用してみてください。