Zenn
🈂️

JavaScriptで解くLeetCode：Is Subsequence

2024/12/31に公開
JavaScript
LeetCode
tech

このシリーズでは、プログラミング学習サイト LeetCode に掲載されている問題の中から良問を厳選し、JavaScript を使って解説していきます。

今回は、Arai60に収録されている「Is Subsequence」の問題を、JavaScriptでどのように実装するか解説します。

問題の概要

LeetCode の 392. Is Subsequence では、2つの文字列 s と t が与えられたときに、以下を判定します。

「文字列 s は、文字列 t の subsequence（部分文字列）として存在するか？」

ここで「subsequence（部分文字列）」とは、元の文字列から一部の文字を取り除き、残った文字の相対的な順序を変えずに並べた文字列のことをいいます。

たとえば、

  • s = "abc", t = "ahbgdc" → true
    • "ahbgdc" の中から "a", "b", "c" を順番に取り出すことが可能。
  • s = "axc", t = "ahbgdc" → false
    • t の中に順番通りの "a", "x", "c" が存在しない。

制約

  • 0 <= s.length <= 100
  • 0 <= t.length <= 10^4
  • s と t は小文字英アルファベット（a～z）のみで構成される

subsequence（部分文字列）とは？

subsequence（部分文字列）とは、オリジナルの文字列から一部の文字を削除してできる文字列のことを指します。
たとえば、

  • 元の文字列："ahbgdc"
  • "abc" は、"a" → "h" → "b" → "g" → "d" → "c" という順番を変えないまま、一部の文字（ここでは "h", "g", "d"）をスキップすることで作れるため、部分文字列となります。
  • しかし、"axc" の場合は、"ahbgdc" の中に "a" → "x" → "c" という並びがない（"x" が存在しない）ため、部分文字列ではないと判定されます。

アルゴリズムの概要

この問題を解くうえで、シンプルかつ理解しやすいのが2 つのポインタ（インデックス）を使う方法です。

  1. ポインタの初期化
    • sIndex（文字列 s の走査位置）
    • tIndex（文字列 t の走査位置）
  2. 文字の比較＆移動
    • t を先頭から末尾まで走査 (tIndex を 0 から t.length - 1 まで進める)。
    • t[tIndex] と s[sIndex] が一致すれば、sIndex を 1 進める（次の文字を探す）。
    • いずれにしても tIndex は 1 進める。
  3. 全ての文字が見つかったかどうかの判定
    • sIndex が s.length に達した時点で、すべての文字を正しく探し出せたことになるため true。
    • t を最後まで走査しても sIndex が s.length に達しなかった場合は false。

コード例

/**
 * sがtの部分文字列であるかを判定する関数
 * @param {string} s - 判定対象の文字列
 * @param {string} t - 基本となる文字列
 * @return {boolean} - sがtの部分文字列であればtrue、そうでなければfalse
 */
function isSubsequence(s, t) {
    // sが空文字の場合は常にtrueを返す（どんな文字列でも空文字は部分文字列）
    if (s.length === 0) return true;

    // s と t のインデックスを初期化
    let sIndex = 0;
    let tIndex = 0;

    // tを走査しながらsの文字を探す
    while (tIndex < t.length) {
        // 現在のtの文字とsの文字が一致する場合
        if (t[tIndex] === s[sIndex]) {
            sIndex++; // sの次の文字を探す
            // sの全ての文字を見つけた場合はtrueを返す
            if (sIndex === s.length) {
                return true;
            }
        }
        tIndex++; // tのインデックスは毎回進める
    }

    // sIndexが最後まで到達しなかった場合はfalse
    return false;
}

// 使用例
console.log(isSubsequence("abc", "ahbgdc")); // 出力: true
console.log(isSubsequence("axc", "ahbgdc")); // 出力: false

コードのポイント解説

  1. 空文字特例 (if (s.length === 0) return true;)

    • 文字列 s が空の場合、常に部分文字列とみなされるため true を返します。

  2. 2 つのインデックスで比較

    • while (tIndex < t.length) { … } で t 全体を走査します。
    • if (t[tIndex] === s[sIndex]) のときだけ sIndex++ を行い、次の文字へ移行します。

  3. 早期終了

    • sIndex が s.length になった段階で、必要な文字をすべて見つけたということなので、すぐに true を返すことができます。

  4. 最終判定

    • 走査が終わっても sIndex < s.length のままなら、 t の中で s の文字をすべて順番通りに見つけられなかったということになるので false を返します。

時間計算量と空間計算量

  • 時間計算量: t の長さを n、s の長さを m とすると、最悪の場合でも t を 1 回走査するため O(n) となります。
  • 空間計算量: 追加のデータ構造は使わないため O(1) です。

（m は最大でも s.length ぶん比較が必要ですが、m <= n であり、全体としては主に n の長さに依存します。）

例での動作確認

例1: s = "abc", t = "ahbgdc"

  • 初期: sIndex = 0, tIndex = 0
    • s[sIndex] = "a", t[tIndex] = "a" → 一致
    • sIndex = 1, tIndex = 1
  • s[sIndex] = "b", t[tIndex] = "h" → 不一致
    • tIndex = 2
  • s[sIndex] = "b", t[tIndex] = "b" → 一致
    • sIndex = 2, tIndex = 3
  • s[sIndex] = "c", t[tIndex] = "g" → 不一致
    • tIndex = 4
  • s[sIndex] = "c", t[tIndex] = "d" → 不一致
    • tIndex = 5
  • s[sIndex] = "c", t[tIndex] = "c" → 一致
    • sIndex = 3 (== s.length) → true

例2: s = "axc", t = "ahbgdc"

  • 初期: sIndex = 0, tIndex = 0
    • s[sIndex] = "a", t[tIndex] = "a" → 一致 → sIndex = 1, tIndex = 1
  • s[sIndex] = "x", t[tIndex] = "h" → 不一致 → tIndex = 2
  • s[sIndex] = "x", t[tIndex] = "b" → 不一致 → tIndex = 3
  • s[sIndex] = "x", t[tIndex] = "g" → 不一致 → tIndex = 4
  • s[sIndex] = "x", t[tIndex] = "d" → 不一致 → tIndex = 5
  • s[sIndex] = "x", t[tIndex] = "c" → 不一致 → tIndex = 6
  • tIndex = 6 は t.length = 6 に到達し、ループ終了。
  • sIndex は 1 のまま（"x" を見つけられなかった）→ false

まとめ

  • 部分文字列とは: 元の文字列から一部の文字を取り除いて作られ、残った文字の順序はそのまま。
  • アルゴリズムの核: 2 つのポインタ（sIndex, tIndex）を使って、t を走査しながら s の文字を順番にチェックする。
  • 時間計算量: O(n) でシンプルに実装できる。
  • 応用: 大量の s を判定する場合には、あらかじめ t の文字の出現位置をまとめたデータ構造を作成し、二分探索を行う方法がある（今回のコードは単一の s を判定する想定）。

「Is Subsequence」は基本的な文字列処理問題ですが、部分文字列の概念を理解する入門に最適です。

実際、多くの応用問題でも同様の手法（2 つのポインタや文字インデックス管理）が使われるので、ぜひしっかりとマスターしてください。

Discussion