Regular Expression Matching
文字列 s とパターン p が与えられます。パターンでは、文字は同じ文字に一致し、ドット . は任意の1文字に一致します。また、アスタリスク * は、その直前にある文字またはドットの要素が0個以上続くことを意味します。パターンが s 全体に一致する場合は true を、そうでない場合は false を返してください。
関数
- sstring
- 照合する文字列（小文字のみ）
- pstring
- 文字、ドット、星のパターン
- 戻り値boolean
- p が s のすべてに一致する場合は true、そうでなければ false
制約
1 ≤ s.length ≤ 10001 ≤ p.length ≤ 1000sには小文字の英字のみが含まれています。pには小文字の英字、.、*のみが含まれます。- すべての
*は文字または.の後に続くため、pが*で始まることはなく、アスタリスクが2つ連続することもありません。
例
- 入力
- s = "moon"p = "mo*n"
- 出力
- true
- 説明
o*は 2 つの o を両方とも取るので、m、o*、n でmoonと正確につづれます。
- 入力
- s = "tree"p = "t.e"
- 出力
- false
- 説明
t.eはtreeの始まりであるtreに一致しますが、最後の e が余り、マッチはs全体を覆わなければなりません。
- 入力
- s = "sky"p = "z*s.*y"
- 出力
- true
- 説明
z*は z を 0 個取り、s は s に一致し、.*は k を取り、y は y に一致します。
発展問題
同じ表で、+にも対応できますか？これは、その前の要素が1つ以上繰り返されることを意味します。
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
- 文字とそれに続く
*を1つの単位として扱います。その単位をsの次の文字と比較するとき、できることは何の2つですか？ この単位は何も一致させずにスキップすることも、1文字に一致してその場にとどまり、さらに文字を受け取れる状態にすることもできます。その他のパターン文字はすべて、ちょうど1文字に一致しなければなりません。各アスタリスクで両方の動きを試すと、多くの作業が繰り返されます。
sの各接頭辞がpの各接頭辞に一致するかどうかを表に記録します。まず空文字列の行を埋めます。この行では、a*b*のようなパターンだけが一致します。アスタリスクのセルは、2列左のセルが真である場合、またはその要素が文字と一致し、真である場合に真となります。
解説
スターは任意の数の文字に一致でき、適切な数はその後に何が続くかによって決まります。文字とそのスターを、2つの動作を持つ1つの単位として扱います。つまり、スキップするか、文字を1つ消費してその位置にとどまるかです。sの各接頭辞がpのどの接頭辞に一致するかを示す表を使えば、すべての選択肢を一度ずつ試せます。
再帰で左から一致させる
正しいが、最大のテストでは終わらない
考え方
接尾辞を比較します。match(i, j)は、s[i:]がp[j:]に一致するかどうかを示します。アスタリスクの付いていない文字またはドットはs[i]に一致し、残りも一致しなければなりません。x*という単位は、0個を選んで読み飛ばすか、s[i]を消費して同じ単位にとどまります。これにより、1つのアスタリスクで任意の数の文字を扱えます。この2つの分岐ですべての選択肢を網羅するため、一致を見逃すことはありません。
アスタリスクがあるたびに、探索は2つに分岐します。30個のaに対して、a*を10個並べ、その後にbを置いたパターンを照合すると、再帰処理はfalseと答えるまでに、文字をアスタリスク間で割り振る約8.5 × 10^8通りを試します。しかし、異なる組(i, j)は(n+1) × (m+1)個しかありません。
アルゴリズム
iとjから始まる接尾辞に対して、match(i, j)を記述します。jがpの末尾を過ぎている場合、iがsの末尾を過ぎているかどうかを返します。s[i]が存在し、p[j]がs[i]またはドットであるかどうかをfirstに設定します。p[j+1]がアスタリスクの場合、match(i, j+2)またはfirst and match(i+1, j)を返します。- それ以外の場合は、
first and match(i+1, j+1)を返します。答えはmatch(0, 0)です。
def isMatch(s, p):
n, m = len(s), len(p)
def match(i, j):
# Does s[i:] match p[j:]?
if j == m:
return i == n
first = i < n and p[j] in (s[i], ".")
if j + 1 < m and p[j + 1] == "*":
# use p[j] zero times, or let it eat s[i] and stay on the same x*
return match(i, j + 2) or (first and match(i + 1, j))
return first and match(i + 1, j + 1)
return match(0, 0)接頭辞の表を埋める
考え方
dp[i][j]は、sの最初のi文字がpの最初のj文字に一致するかどうかを表すとします。dp[0][0]はtrueです。0行目では、空文字列がパターンの接頭辞に一致するのは、その中のすべての要素にアスタリスクが付いている場合だけです。たとえばz*やa*b*のような場合です。
p[j-1]の文字またはドットはs[i-1]に一致する必要があり、残りの部分も一致する必要があります。つまり、左上のセルであるdp[i-1][j-1]です。要素x = p[j-2]にアスタリスクが付いている場合、2つの処理があります。0回使う場合はx*を取り除きます。つまりdp[i][j-2]です。もう1回使う場合は、xがs[i-1]に一致すれば、短い文字列に対して同じx*を残して照合します。つまり、1つ上のセルであるdp[i-1][j]です。使うたびに、アスタリスクの列を1つ上に進みます。skyとz*s.*yの場合、z*s.*の列は、0回使うことでsに対してtrueになり、その後、1つずつ上に進むことでskとskyに対してtrueになります。
各セルは1つ上の行または左側のセルを参照するため、行ごとに埋めていけば、必要な値がそろった状態で処理できます。
アルゴリズム
(n+1) × (m+1)個の false 値でテーブルdpを作成し、dp[0][0]を true に設定します。jを 2 からmまで動かし、p[j-1]がアスタリスクで、dp[0][j-2]が true の場合は、dp[0][j]を true に設定します。i ≥ 1かつj ≥ 1の各セルについて、p[j-1]がアスタリスクの場合は、そのセルをdp[i][j-2]または（p[j-2]がs[i-1]と一致し、dp[i-1][j]が true）に設定します。- それ以外の場合は、そのセルを（
p[j-1]がs[i-1]と一致する）かつdp[i-1][j-1]に設定します。 dp[n][m]を返します。
def isMatch(s, p):
n, m = len(s), len(p)
# dp[i][j]: do the first i letters of s match the first j characters of p?
dp = [[False] * (m + 1) for _ in range(n + 1)]
dp[0][0] = True # an empty pattern matches an empty string
for j in range(2, m + 1):
# an empty string matches only patterns like x*y*z*
dp[0][j] = p[j - 1] == "*" and dp[0][j - 2]
for i in range(1, n + 1):
for j in range(1, m + 1):
if p[j - 1] == "*":
zero = dp[i][j - 2] # use p[j-2] zero times
more = p[j - 2] in (s[i - 1], ".") and dp[i - 1][j] # one more copy eats s[i-1]
dp[i][j] = zero or more
else:
dp[i][j] = p[j - 1] in (s[i - 1], ".") and dp[i - 1][j - 1]
return dp[n][m]2 行だけを残す
考え方
行 i が読み取るのは、行 i-1 の2つのセル（対角のセルとその上のセル）に加えて、自分自身の2つ左のセルだけです。prev と cur の2つの配列を保持し、s の各文字の処理後に入れ替えます。コピーが0個の場合は cur[j-2]、コピーをもう1つ追加する場合は prev[j]、通常の一致の場合は prev[j-1] です。メモリ使用量は約10^6個のセルから、1001個のセルを持つ2行分に減ります。文字列とパターンは異なる役割を持つため、行を短くする目的で入力を入れ替えることはできません。
アルゴリズム
prevにテーブルの0行目を格納します。sの各文字について、cur[0]をfalseに設定し、1つ上の行のprevを参照しながら、テーブルの規則に従ってcur[1..m]を埋めます。prevとcurを入れ替えます。prev[m]を返します。
def isMatch(s, p):
n, m = len(s), len(p)
# prev[j]: do the letters of s before the current one match the first j characters of p?
prev = [False] * (m + 1)
prev[0] = True # row 0: the empty string
for j in range(2, m + 1):
prev[j] = p[j - 1] == "*" and prev[j - 2] # only patterns like x*y*z* match it
for i in range(1, n + 1):
cur = [False] * (m + 1) # cur[0] stays False: an empty pattern matches no letters
for j in range(1, m + 1):
if p[j - 1] == "*":
zero = cur[j - 2] # use p[j-2] zero times
more = p[j - 2] in (s[i - 1], ".") and prev[j] # one more copy eats s[i-1]
cur[j] = zero or more
else:
cur[j] = p[j - 1] in (s[i - 1], ".") and prev[j - 1]
prev = cur
return prev[m]
落とし穴と境界ケース
- アスタリスクに、可能な限り多くの文字を取らせること。
a*aはaaaにマッチしますが、貪欲なa*が3文字すべてを消費し、最後の a が失敗します。 - もう1つコピーを取るために
dp[i-1][j-2]を読むこと。これではアスタリスクが取れる文字は最大1文字になり、aaとa*の照合結果は false になります。 - 最初のセル以降、行0を false のままにすること。すると、b と
a*bの照合は失敗します。b がマッチするには、a*が空の接頭辞にマッチする必要があるからです。 s[i-1]を、アスタリスクの要素であるp[j-2]ではなく、アスタリスク自体と比較すること。すると、a とa*の照合は失敗します。- 2行バージョンで
cur[0]を false にリセットしないこと。入れ替え後、基底行の true が残ることがあり、aabとbの照合結果が true になります。
よくある質問3
正規表現マッチングの時間計算量はどのくらいですか？
表を使った解法は、長さがnの文字列と長さがmのパターンに対して、各セルが他のセルを最大2つ参照するため、O(n × m)時間かかります。表全体にはO(n × m)のメモリが必要ですが、2行を使えばO(m)で済みます。単純な再帰では、星印が多数あるパターンで指数時間かかることがあります。
これはワイルドカードマッチングとどう違いますか？
ファイル名のパターンと同様に、ワイルドカードマッチングでは、* は単独で任意の長さの文字列に一致し、? は1文字に一致します。ここでの * は直前の要素だけを繰り返し、任意のテキストは .* です。どちらも接頭辞を使った表を使用しますが、ワイルドカードのアスタリスクは dp[i][j-1] または dp[i-1][j] を参照します。
なぜ言語の正規表現ライブラリを使わないのでしょうか？
面接官が求めているのはアルゴリズムであり、ライブラリ関数の呼び出しではありません。多くの正規表現エンジンも、最初の方法で使った遅い再帰処理であるバックトラッキングによって照合するため、a* を10個並べて、その後に b を続けたパターンを、a が長く続く文字列に対して照合すると、処理に何分もかかることがあります。表を使う方法なら、常に O(n × m) で処理が完了します。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def isMatch(s, p):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
s = "moon" p = "mo*n"
期待される出力
true