Pythonで正規表現パターンと文字列の一致を判定するプログラムの書き方

文字列 s と正規表現パターン p が与えられたとき、そのパターンが文字列全体と一致するかどうかを判定する問題を考えてみましょう。ここで扱う正規表現は、次の2つの特殊文字のみをサポートするシンプルなルールに基づいています。

• . (ピリオド): 任意の1文字に一致します。
• * (アスタリスク): 直前の要素の0回以上の繰り返しに一致します。

たとえば、pattern = "h.l*o"、s = "hello" という入力の場合、「.」が「e」に一致し、「l*」が「ll」(0回以上の l の繰り返し)に一致するため、出力は True になります。

解法のアプローチ:再帰によるマッチング

この問題は、再帰関数を使ってパターンと文字列を先頭から順に照合していくことで解くことができます。具体的な手順は以下の通りです。

• n := 文字列 s の長さ
• m := パターン p の長さ
• 再帰関数 dp(i, j) を定義する(i は s の現在位置、j は p の現在位置)
• j が m と等しい場合(パターンを使い切った場合)、i が n と等しいかどうか(文字列も使い切ったか)を返す
• match := i < n かつ(s[i] が p[j] と等しい、または p[j] が "." である)とき true、それ以外は false
• j + 1 < m かつ p[j + 1] が "*" の場合、dp(i, j + 2)(「*」を0回として扱いスキップ)または(match かつ dp(i + 1, j))(「*」を1回以上の繰り返しとして扱う)のいずれかが true なら true を返す
• 上記以外の場合は、match かつ dp(i + 1, j + 1) を返す
• メイン処理では dp(0, 0) の結果を返す

実装例

理解を深めるために、以下の実装例を見てみましょう。

class Solution:
    def solve(self, p, s):
        n = len(s)
        m = len(p)
        def dp(i, j):
            if j == m:
                return i == n
            match = i < n and (s[i] == p[j] or p[j] == ".")
            if j + 1 < m and p[j + 1] == "*":
                return dp(i, j + 2) or (match and dp(i + 1, j))
            return match and dp(i + 1, j + 1)
        return dp(0, 0)
ob = Solution()
pattern = "h.l*o"
s = "hello"
print(ob.solve(pattern, s))

入力

"h.l*o", "hello"

出力

True

コードのポイント

このアルゴリズムの核心は、「*」を含むパターンの処理部分です。「*」の直前の要素は0回でも良いので、まず dp(i, j + 2) を呼び出して「*」とその直前の要素を丸ごとスキップするケース(0回とみなす)を試します。同時に、現在の文字が一致している(match が true)場合は dp(i + 1, j) を呼び出して、パターン位置はそのままに文字列だけを1文字進めることで、「*」を1回以上の繰り返しとして扱うケースも探索します。この2つの分岐により、あらゆる繰り返しの組み合わせを網羅的にチェックでき、正確なマッチング判定が可能になります。