Skip to content

Latest commit

 

History

History

README.md

OK、ではこのコードを図付きで解析していきます。 「DPテーブルの意味」「ループの動き」「* / ? の遷移の違い」をステップごとに可視化します。


1. アルゴリズムの概要

  • dp[j] : s[0..i-1](s の先頭から i 文字)と p[0..j-1](p の先頭から j 文字)が一致するかどうか。
  • prev : 前の行(i-1文字目までの結果)
  • curr : 現在の行(i文字目までの結果)
  • ループの外では 空文字同士の一致先頭の * の特別処理 を行う。

2. 図で見る初期化

例) s = "ab" p = "*b" (m = 2, n = 2)

初期状態 (prev 配列)

prev: [T, ?, ?]   // prev[0] = true(空文字同士一致)
curr: [F, ?, ?]

先頭からの * 初期化処理

for (let j = 1; j <= n; j++) {
    if (p[j - 1] === '*') {
        prev[j] = prev[j - 1];
    }
}

動き

  • j=1 → p[0] = '*' → prev[1] = prev[0] = T
  • j=2 → p[1] = 'b' → 何もしない

結果

prev: [T, T, F]

図解:

   p:   *   b
j: 0   1   2
    ┌───┬───┬───┐
    │ T │ T │ F │
    └───┴───┴───┘

3. メインループ(iループ)

i = 1(s[0] = 'a')

  1. curr[0] = false(pが空でsが非空は不一致)

  2. j=1(p[0] = '*')

curr[1] = prev[1] || curr[0]
         = T       || F
         = T

図解:

'*' → 空を表すなら prev[1] を見る(上方向)
     1文字以上表すなら curr[0] を見る(左方向)
  1. j=2(p[1] = 'b')
'b' == 'a' ? false : (curr[2] = false);

結果

curr: [F, T, F]

入れ替え

prev ← curr

i = 2(s[1] = 'b')

  1. curr[0] = false

  2. j=1(p[0] = '*')

curr[1] = prev[1] || curr[0]
         = T       || F
         = T
  1. j=2(p[1] = 'b')
'b' == 'b'  curr[2] = prev[1] = T

結果

curr: [F, T, T]

4. 最終結果

最後に prev[n](= prev[2])が答え。 prev[2] = true → 一致。


5. DPテーブル全体イメージ

完全2次元表で見るとこうなる(T/Fはtrue/false)

      ""   *    b
""   [T]  [T]  [F]
 a   [F]  [T]  [F]
 b   [F]  [T]  [T]
  • 上方向prev[j])は * が空を表すときの遷移
  • 左方向curr[j-1])は * が文字を消費する遷移
  • 斜め左上(prev[j-1])は ? または同一文字での遷移

6. 遷移パターンの図

      p[j-1]
         |
         v
    ┌──────────────┐
    │ '*' ?         │
    ├──────────────┤
    │ dp[i][j] =    │
    │   dp[i][j-1]  │ ← 左(* が1文字以上を吸収)
    │   OR dp[i-1][j]│ ← 上(* が空を吸収)
    └──────────────┘

    ┌──────────────┐
    │ '?' or match  │
    ├──────────────┤
    │ dp[i][j] = dp[i-1][j-1] │ ← 斜め左上
    └──────────────┘

これを踏まえると、このコードは

  • 行ごとに状態を持ち回すことで O(n) メモリ
  • 遷移は 左 / 上 / 斜め左上 への参照で構成
  • * は分岐(空 or 1文字以上吸収)、? / 同文字は斜め移動 というシンプルな構造になっています。

もし希望なら、この図をs="abc", p="*?c" のケースで全遷移図にして、 実際に true になる経路を線でつないだ可視化も作れます。 その方が理解が深まりますが、やりますか?