JavaScriptで部分列（サブシーケンス）を判定する方法｜2つのポインタを使った効率的な実装

2つの文字列 str1 と str2 が与えられたとき、str1 が str2 の部分列であるかどうかを判定する関数を作成する方法を解説します。

部分列（サブシーケンス）とは？

文字列の部分列とは、元の文字列から一部の文字（0個でも構いません）を削除して作られる新しい文字列のことです。このとき、残った文字同士の相対的な順序は崩してはいけないというルールがあります。

例を挙げてみましょう。

• "ace" は "abcde" の部分列です（b と d を削除すれば ace になります）。
• "aec" は "abcde" の部分列ではありません。a → e → c の順に並んでおらず、元の順序が崩れているためです。

実装例：2つのポインタを使うアプローチ

最もシンプルで効率的な方法は、2つのポインタ（インデックス）を使って両方の文字列を一度だけ走査する手法です。

const str1 = 'ace';
const str2 = 'abcde';

const isSubsequence = (str1, str2) => {
    let i = 0;
    let j = 0;
    while (i < str1.length) {
        if (j === str2.length) {
            return false;
        }
        if (str1[i] === str2[j]) {
            i++;
        }
        j++;
    }
    return true;
};

console.log(isSubsequence(str1, str2));

コードの仕組み

このアルゴリズムは次のように動作します。

1. ポインタ i は str1 の位置を、ポインタ j は str2 の位置を追跡します。
2. str1[i] と str2[j] が一致した場合のみ、i を進めます。
3. ポインタ j は毎回必ず1つ進みます。
4. j が str2 の末尾に到達しても str1 の走査が完了していない場合は、false を返します。
5. ループを抜けて str1 のすべての文字が順番通りに見つかった場合は、true を返します。

計算量

• 時間計算量： O(n) — str2 を最大1回走査するだけです。
• 空間計算量： O(1) — ポインタ2つ分の追加メモリしか使いません。

実行結果

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

true

"ace" は "abcde" の部分列であるため、正しく true が出力されました。この手法は、文字列照合やエディタの補完機能など、さまざまな場面で応用できる基本的なテクニックです。