Skip to content

10. Regular Expression Matching

Directory actions

More options

Directory actions

More options

Latest commit

 

History

History

10. Regular Expression Matching

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
README.md
README.md
 
 
RegularExpressionMatching.py
RegularExpressionMatching.py
 
 
RegularExpressionMatching.ts
RegularExpressionMatching.ts
 
 

README.md

JavaScript + DP解法 を用いて処理し、各処理を図を使って具体的に説明します。

🎯 問題概要（再掲）

  • s：マッチさせたい文字列（例: "aa"）
  • p：正規表現パターン（例: "a*"）

正規表現ルール：

記号 意味
. 任意の1文字にマッチ
* 直前の文字の 0 回以上の繰り返し

🧠 解法方針：動的計画法（DP）

🧩 状態定義

  • dp[i][j] = true ⇔ s[0..i-1]（長さ i の prefix）と p[0..j-1]（長さ j の prefix）がマッチする

🧮 例：s = "aa"、p = "a*"

初期状態

s = " a  a"
     ↑  ↑
i=  1  2

p = " a  *"
     ↑  ↑
j=  1  2

DP テーブルの初期化

"" a *
"" T F T
a F T T
a F F T

📊 ステップ 1：dp[0][0] = true

空文字列同士は常にマッチ。

dp[0][0] = true

📊 ステップ 2：パターンに * がある場合の初期化

  • dp[0][2] = dp[0][0] = true（a* が空文字列にマッチ）
Pattern: "a*"
→ '*' は前の 'a' を0回とみなせるのでOK

📊 ステップ 3：DPテーブルの構築（再帰的に状態更新）

for (let i = 1; i <= m; i++) {
  for (let j = 1; j <= n; j++) {
    ...
  }
}

更新規則（図示）

🔹 case1: 文字一致 or .（1文字マッチ）

if (p[j-1] === s[i-1] || p[j-1] === '.')
→ dp[i][j] = dp[i-1][j-1]

s: ... a
p: ... a
     ↑   ↑
     i   j

🔹 case2: * の場合（0回 or 1回以上）

if (p[j-1] === '*') {
    dp[i][j] = dp[i][j-2]   // * を0回使用
    if (p[j-2] === s[i-1] || p[j-2] === '.')
        dp[i][j] |= dp[i-1][j] // * を1回以上使用
}

Pattern:  a*
          ↑↑
          j-2 j-1

s:     a   a
       ↑
       i-1

✅ 最終的なDPテーブル（例：s="aa", p="a*"）

"" a *
"" ✅ ❌ ✅
a ❌ ✅ ✅
a ❌ ❌ ✅

→ dp[2][2] = true（完全一致）

🖼️ 図による処理まとめ

s = "aa"
p = "a*"

1. dp[0][0] = true          // 空文字列同士マッチ

2. dp[0][2] = true          // a* → *は0回で空文字にマッチ

3. dp[1][1] = true          // s[0] = a, p[0] = a

4. dp[1][2] = true          // '*' で1回以上の a

5. dp[2][2] = true          // '*' でさらに1回

📌 結果

console.log(dp[s.length][p.length]); // true

🔁 応用例

s = "ab", p = ".*"

  • . → 任意の文字
  • * → 何回でも繰り返し → すべての文字列にマッチ
dp[2][2] = true

🧠 メモリ＆計算量

  • 時間：O(m × n)
  • 空間：O(m × n)
    • 制約が 20 以下なので問題なし（最大 400 要素）