Pythonでのワイルドカードマッチング：動的計画法を使った実装方法

入力文字列 s と、もう一つの入力文字列 p があるとします。s が対象となる文字列で、p はパターンです。この記事では、文字列がパターンに一致するかどうかを判定するメソッドを Python で実装します。具体的には、「?」や「*」といったワイルドカード文字をサポートする正規表現マッチングを実装していきます。

ワイルドカードのルール

• 「?」（クエスチョンマーク）：任意の1文字に一致します。
• 「*」（アスタリスク）：0個以上の任意の文字列に一致します。

例えば、s = "aa"、p = "a?" という入力の場合、結果は True になります。同じ入力文字列に対して、パターンが "?*" の場合も True となります。

解法のアプローチ：動的計画法

この問題は動的計画法（DP）を使うことで効率的に解けます。以下の手順に従います。

1. ss を s の長さ、ps を p の長さとします。
2. (ss + 1) × (ps + 1) のサイズの2次元配列 dp を作成し、すべて False で初期化します。
3. s と p の先頭に空白を1文字追加します。これにより、空文字列の場合も含めてインデックスの扱いが簡単になります。
4. i を 1 から ps まで繰り返します。p[i] が「*」の場合、dp[0][i] = dp[0][i - 1] とします（空文字列に対しても「*」は連続してマッチできるためです）。
5. i を 1 から ss まで、j を 1 から ps まで二重ループで繰り返します。
   • s[i] と p[j] が一致する、または p[j] が「?」の場合：dp[i][j] = dp[i - 1][j - 1]
   • それ以外で p[j] が「*」の場合：dp[i][j] = dp[i - 1][j] と dp[i][j - 1] のいずれか（どちらか一方でも True なら True）
6. 最後に dp[ss][ps] を返します。これが全体のマッチング結果になります。

Pythonでの実装例

以下のコードを見ると、より理解が深まるでしょう。

class Solution(object):
    def isMatch(self, s, p):
        sl = len(s)
        pl = len(p)
        dp = [[False for i in range(pl+1)] for j in range(sl+1)]
        s = " "+s
        p = " "+p
        dp[0][0]=True
        for i in range(1,pl+1):
            if p[i] == '*':
                dp[0][i] = dp[0][i-1]
        for i in range(1,sl+1):
            for j in range(1,pl+1):
                if s[i] == p[j] or p[j] == '?':
                    dp[i][j] = dp[i-1][j-1]
                elif p[j]=='*':
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1])
        return dp[sl][pl]

ob = Solution()
print(ob.isMatch("aa", "a?"))
print(ob.isMatch("aaaaaa", "a*"))

入力

"aa", "a?"
"aaaaaa", "a*"

出力

True
True

まとめ

このアルゴリズムの計算量は、時間・空間ともに O(ss × ps) です。「*」が「直前の文字を消費しない（dp[i][j-1]）」のか「現在の文字を消費する（dp[i-1][j]）」のかという2通りのケースを考慮することで、単純な貪欲法では対応が難しいバックトラックの問題を、動的計画法によって効率よく解決できます。