🔍 ワイルドカードパターンマッチング解析

インタラクティブデモ

文字列 (s):

パターン (p):

📊 アルゴリズムの流れ

1. DPテーブル初期化

→

2. ベースケース設定

→

3. DP計算

→

4. 結果取得

🎯 Example 1: s="aa", p="*"

ステップバイステップ解析

ステップ1: DPテーブル初期化
サイズ (3×2) のテーブルを作成し、全てfalseで初期化

	ε	*
ε	T	T
a	F	T
aa	F	T

処理ロジック:
• dp[0][0] = true (空文字列と空パターンはマッチ)
• dp[0][1] = true ('*'は空文字列にもマッチ)
• dp[1][1] = dp[1][0] || dp[0][1] = false || true = true
• dp[2][1] = dp[2][0] || dp[1][1] = false || true = true

🎯 Example 2: s="adceb", p="ab*"

True (マッチ)

False (マッチしない)

⚡ 時間・空間計算量解析

時間計算量: O(m × n)

• m = 文字列の長さ, n = パターンの長さ

• 各セルを一度だけ計算するため線形時間

空間計算量: O(m × n)

• DPテーブルのサイズに依存

• 最適化: O(n)に削減可能（前の行のみ保持）

🔧 核心処理の詳細

                if (pChar === '*') { // '*'の2つの解釈: // 1. 空文字列として扱う: dp[i][j-1] // 2.
                1文字以上として扱う: dp[i-1][j] dp[i][j] = dp[i][j - 1] || dp[i - 1][j]; } else if
                (pChar === '?' || pChar === sChar) { // '?'は任意の1文字、または完全一致 dp[i][j] =
                dp[i - 1][j - 1]; }
            

🌟 '*'の処理が重要な理由

dp[i][j-1]: '*'を空文字列として解釈

dp[i-1][j]: '*'を現在の文字を含む文字列として解釈

この2つの論理和により、'*'の柔軟性を完全に表現