JavaScriptで2つの配列から共通する最長シーケンスを見つける方法

問題の概要

リテラル値を要素とする2つの配列(arr1 と arr2)を受け取る JavaScript 関数を作成する必要があります。

この関数は、両方の配列に共通して現れる最長の要素列(ストリーク)を見つけ出し、その要素を新しい配列として返します。共通する要素が存在しない場合は空文字列を含む配列が返されます。

入力例

const arr1 = ['a', 'b', 'c', 'd', 'e'];
const arr2 = ['k', 'j', 'b', 'c', 'd', 'w'];

この場合、両方の配列に「b」「c」「d」がこの順序で共通して現れているため、期待される出力は以下のようになります。

出力例

const output = ['b', 'c', 'd'];

解決アプローチ:動的計画法(DP)

この問題は、最長共通部分列(Longest Common Subsequence:LCS)を求める古典的なアルゴリズムである動的計画法を使って効率的に解くことができます。

基本的な考え方は以下の通りです。

1. 2つの配列を結合して文字列化し、比較しやすい形に変換する
2. (str2.length + 1) × (str1.length + 1) のサイズを持つ2次元のDPテーブルを作成する
3. 各セルには、そこまでの位置における共通部分列の長さを格納する
4. 文字が一致する場合は「左上のセルの値 + 1」を記録し、一致しない場合は「上または左のセルのうち大きい方」の値を引き継ぐ
5. 最後にテーブルを右下から逆方向にたどり、実際の共通シーケンスを復元する

サンプルコード

以下が実装コードです。

const arr1 = ['a', 'b', 'c', 'd', 'e'];
const arr2 = ['k', 'j', 'b', 'c', 'd', 'w'];
const longestCommonSubsequence = (arr1 = [], arr2 = []) => {
    let str1 = arr1.join('');
    let str2 = arr2.join('');
    const arr = Array(str2.length + 1).fill(null).map(() => Array(str1.length + 1).fill(null));
    for (let j = 0; j <= str1.length; j += 1) {
        arr[0][j] = 0;
    }
    for (let i = 0; i <= str2.length; i += 1) {
        arr[i][0] = 0;
    }
    for (let i = 1; i <= str2.length; i += 1) {
        for (let j = 1; j <= str1.length; j += 1) {
            if (str1[j - 1] === str2[i - 1]) {
                arr[i][j] = arr[i - 1][j - 1] + 1;
            } else {
                arr[i][j] = Math.max(
                    arr[i - 1][j],
                    arr[i][j - 1],
                );
            }
        }
    }
    if (!arr[str2.length][str1.length]) {
        return [''];
    }
    const res = [];
    let j = str1.length;
    let i = str2.length;
    while (j > 0 || i > 0) {
        if (str1[j - 1] === str2[i - 1]) {
            res.unshift(str1[j - 1]);
            j -= 1;
            i -= 1;
        }
        else if (arr[i][j] === arr[i][j - 1]) {
            j -= 1;
        }
        else {
            i -= 1;
        }
    }
    return res;
};
console.log(longestCommonSubsequence(arr1, arr2));

実行結果

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

['b', 'c', 'd']

コードのポイント

・時間計算量: O(m × n) — m と n はそれぞれ2つの配列の長さです
・空間計算量: O(m × n) — DPテーブル用の2次元配列が必要です
・ 共通要素がひとつもない場合、テーブルの右下の値が 0 になるため、その時点で [''] を早期リターンしています
・ 復元処理では res.unshift() を使うことで、逆順にたどった結果を正しい順序で組み立てています

この手法は、差分比較ツールやファイルのバージョン管理システムなど、さまざまな場面で応用される強力なアルゴリズムです。