Regular Expression Matching
文字列 s とパターン p が与えられます。パターンでは、文字は同じ文字に一致し、ドット . は任意の1文字に一致します。また、アスタリスク * は、その直前の要素（文字またはドット）が0回以上繰り返されることを意味します。パターンが s の一部だけでなく全体に一致する場合は true を返し、そうでない場合は false を返してください。
関数
- sstring
- 照合する文字列。小文字のみ
- pstring
- 文字、ドット、アスタリスクのパターン
- 戻り値boolean
- true は p が s のすべてに一致する場合、それ以外は false
制約
1 ≤ s.length ≤ 10001 ≤ p.length ≤ 1000sには小文字の英字のみが含まれます。pには、小文字の英字、.、*のみが含まれます。- すべての
*は文字または.の後に続くため、pが*で始まることはなく、アスタリスクが連続することもありません。
例
- 入力
- s = "moon"p = "mo*n"
- 出力
- true
- 説明
o*は両方の o を取るので、m、o*、n で正確にmoonと綴れます。
- 入力
- s = "tree"p = "t.e"
- 出力
- false
- 説明
t.eは3文字の文字列にのみ一致します。t、任意の文字、そしてeです。treeの先頭にあるtreには一致しますが、最後のeは残り、s全体を覆う一致でなければなりません。
- 入力
- s = "sky"p = "z*s.*y"
- 出力
- true
- 説明
z*は z を0個取ります。s は s に一致し、.*は k を取り、y は y に一致します。アスタリスクが付いた文字は何も表さないこともできるため、skyに現れない z はコストになりません。
提出時に隠しテスト+29件
発展問題
同じ表を使って、その直前の要素が1回以上繰り返されることを示す + にも対応できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
文字とそれに続く
*を1つの単位として扱います。その単位をsの次の文字と比較するとき、できることは2つあります。何でしょうか？この単位は何にも一致せずにスキップされることも、1文字に一致してその位置にとどまり、さらに文字を受け取れる状態になることもあります。それ以外のパターン文字は、すべて文字1つに正確に一致する必要があります。各アスタリスクで両方の動きを試すと、多くの作業が繰り返されます。
sの各接頭辞がpの各接頭辞に一致するかどうかを表に格納します。まず空文字列の行を埋めます。この行で一致するのは、a*b*のようなパターンだけです。アスタリスクのセルが真となるのは、2列左のセルが真である場合、またはその要素が文字と一致し、真上のセルが真である場合です。
解説
スターは任意の個数のコピーに一致でき、適切な個数はその後に続くものによって決まります。可能な限り多く取る方法ではうまくいきません。aaaに対して、パターンa*aではa*が3文字すべてを取ってしまい、最後のaに何も残りません。これを解決する考え方は、文字とそのスターを2つの動きを持つ1つの単位として扱うことです。つまり、それを飛ばすか、1文字を取り込んで同じ位置にとどまるかです。表にsの各接頭辞がpの各接頭辞に一致するかを記録することで、すべての選択肢を一度ずつ試せます。表は2行あれば十分です。
再帰を使って左から一致させる
正しいが、最大のテストでは終わらない
考え方
match(i, j)が、接尾辞s[i:]が接尾辞p[j:]に一致するかどうかを返すものとします。パターンを使い切った場合、文字列も使い切っている場合にのみ一致します。そうでなければfirstを計算します。つまり、文字s[i]があり、p[j]がその文字かドットであるということです。
次に、1文字先を見ます。p[j+1]がアスタリスクなら、p[j]*は2つの動きを持つ1つの単位です。0個取ることができます。つまり、match(i, j+2)で両方の文字を飛ばします。あるいは、firstが成り立つなら、1個取ることができます。つまり、s[i]を消費し、match(i+1, j)で同じ単位にとどまり、次を取れる状態にします。jにとどまることで、1つのアスタリスクが文字を1つずつ、任意の個数取れるようになります。アスタリスクがなければ、p[j]はちょうど1文字に一致しなければなりません。つまり、first and match(i+1, j+1)です。
遅いのは、アスタリスクがあるたびに探索が2つに分かれ、失敗が見つかるのはたいてい最後になってからだからです。30個のaに、a*を10個並べ、その後にbを続けたパターンを考えてみましょう。再帰処理は、30個のaの一部または全部を10個のアスタリスクに割り当てるあらゆる方法を試します。その数は約8.5 × 10^8通りで、falseと答えるまでに約2 × 10^9回の呼び出しを行います。大きなテストでは文字数は1000です。それでも、異なるペア(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 文字に一致するかどうかを表します。インデックス 0 は空の接頭辞を表します。
基底行と基底列。 dp[0][0] は true です。空のパターンは空の文字列に一致します。列 0 はその下では false です。空のパターンは文字に一致できないためです。行 0 は少し注意が必要です。パターンの接頭辞が空の文字列に一致するのは、その中のすべての要素が z* や a*b* のようにスター付きの場合だけです。したがって、p[j-1] がスターで、dp[0][j-2] が true のとき、dp[0][j] は true です。
遷移。 p[j-1] が文字またはドットの場合、それは最後の文字 s[i-1] と一致し、残りも一致する必要があります。つまり、対角の dp[i-1][j-1] です。p[j-1] がスターの場合、その要素は x = p[j-2] で、スターには2つの動きがあります。コピー0個： パターンから x* を取り除きます。つまり、左に2つのセルの dp[i][j-2] です。もう1つコピー： x が s[i-1] と一致するなら、その文字はコピーの1つです。同じ x* でより短い文字列の照合を続ける必要があるため、同じ列の真上にあるセル dp[i-1][j] を参照します。コピー1つにつきその列を1段上がることになり、これが1つのスターで任意の数の文字を扱える仕組みです。
sky と z*s.*y の表を示します。列は接頭辞 ""、z、z*、z*s、z*s.、z*s.*、z*s.*y に対応します（T は true、F は false）。行 "" は [T, F, T, F, F, F, F] です。空になれるのは z* だけです。行 s は [F, F, F, T, F, T, F] です。対角上で上の z* が空になり、s が s に一致します。その後、.* はコピーを0個取ります。行 sk は [F, F, F, F, T, T, F] です。z*s.* のセルは、ドットが k を取り込む「もう1つのコピー」によって true になります。真上にある T を参照します。行 sky は [F, F, F, F, F, T, T] です。同じようにドットスターが y を取り込み、列をもう1段上がります。その後、対角上で y が y に一致します。最後のセルは true です。
各セルは1つ上の行または左側のセルを参照するため、行ごとに左から右へ埋めていけば、参照先はすでに計算されています。セル数は (n+1) × (m+1) で、最大のテストでは約 10^6 個となり、各セルの計算量は一定です。
アルゴリズム
(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つ左のセルを1つ読み取ります。それより上の行は、以後読み取ることはありません。2つの配列を用意します。完成した行用の prev と、埋めている最中の行用の cur です。s の各文字の処理後に、この2つを入れ替えます。遷移は変わりません。0回のコピーは cur[j-2]、コピーをもう1回行う場合は prev[j]、通常の一致は prev[j-1] です。
空文字列の基底行として prev を初期化します。各行の開始時に cur[0] を false に設定します。入れ替え後、cur には古い行が入っており、基底行の最初の要素は true だからです。
各行には m + 1 個の要素があるため、メモリ使用量は約10^6個のセルから、1001個の要素を持つ2つの行に減ります。編集距離とは異なり、行を短くするために2つの入力を入れ替えることはできません。文字列とパターンでは役割が異なるからです。
アルゴリズム
- ベース行を設定して
prevを埋めます。0ではtrueとし、p[j-1]がアスタリスクで、prev[j-2]がtrueの場合はjでもtrueとします。 sの各文字について、cur[0]をfalseに設定します。cur[1..m]を埋めます。アスタリスクのセルはcur[j-2]または（要素が一致し、prev[j]がtrue）です。それ以外のセルは（要素が一致し）、prev[j-1]がtrueです。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 になります。アスタリスクの列にとどまりましょう。dp[i-1][j]。 - 最初のセル以外、行0をすべて false のままにしてしまうこと。そうすると、
bはa*bにマッチしません。b の前にある空の接頭辞にマッチするために、a*が必要だからです。 s[i-1]をアスタリスクそのものと比較し、その要素p[j-2]と比較しないこと。- ファイル名パターンのように、
*を「任意のテキスト」として扱うこと。ここでは直前の要素だけを繰り返します。任意のテキストを表すのは.*です。 - 部分一致を受け入れてしまうこと。
t.eはtreeの先頭部分に当てはまりますが、文字が1つ残るため答えは false です。 - 2行バージョンで
cur[0] = falseを忘れること。最初の入れ替えの後、cur[0]には基底行の true が入っています。
よくある質問4
正規表現マッチングの時間計算量はどのくらいですか？
テーブルを使う解法の実行時間は O(n × m) です。ここで、n は s の長さ、m は p の長さです。各セルが参照するのは最大2つのセルだからです。テーブル全体には O(n × m) のメモリが必要ですが、2行を使えば O(m) で済みます。単純な再帰では、アスタリスクが多いパターンの場合、実行時間が指数関数的に増えることがあります。
なぜ星形のセルは斜めのセルではなく、真上のセルを読み取るのですか？
上のセル dp[i-1][j] は、s の文字が1つ少なく、星印はそのまま残っている同じパターンです。したがって、星印が s[i-1] を取り込んだ後、列を上に進みながら s[i-2] も取り込むことができ、以降も同様です。対角線上のセル dp[i-1][j-2] は、1文字分の後で星印を取り除くため、任意の数ではなく、ちょうど1回の出現を許します。
これはワイルドカードマッチングとどう違いますか？
ファイル名のパターンと同様に、ワイルドカードマッチングでは * は単独で任意の長さの文字列に一致し、? は1文字に一致します。ここでは * は直前の要素だけを繰り返し、任意のテキストに一致するパターンは .* です。どちらも接頭辞に対する表を使って解きますが、アスタリスクの遷移は異なります。ワイルドカードでは dp[i][j-1] または dp[i-1][j] を読み取ります。
なぜその言語の正規表現ライブラリを使わないのでしょうか？
面接官が求めているのはアルゴリズムであり、ライブラリの呼び出しではありません。また、実際のリスクもあります。多くの正規表現エンジンはバックトラッキングによってマッチングを行います。これは最初の方法で使われている、処理の遅い再帰です。a*を10個並べた後にbを続けたパターンを、aが長く連続する文字列に対して使うと、そのようなエンジンでは処理に数分かかることがあります。表を使う方法なら、必ずO(n × m)で終了します。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def isMatch(s, p):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
s = "moon" p = "mo*n"
期待値
true