Regular Expression Matching

Q: Apa kompleksitas waktu Pencocokan Ekspresi Reguler?

Solusi tabel berjalan dalam waktu O(n × m) untuk string dengan panjang n dan pola dengan panjang m , karena setiap sel membaca paling banyak dua sel lainnya. Solusi ini membutuhkan memori O(n × m) untuk tabel lengkap, atau O(m) dengan dua baris. Rekursi biasa dapat membutuhkan waktu eksponensial untuk pola dengan banyak tanda bintang.

Q: Apa bedanya dengan pencocokan wildcard?

Dalam pencocokan wildcard, seperti pada pola nama file, * berdiri sendiri dan cocok dengan rangkaian karakter apa pun, sedangkan ? cocok dengan satu karakter. Di sini, * hanya mengulang elemen sebelumnya, dan teks apa pun ditulis sebagai .* . Keduanya menggunakan tabel atas prefiks, tetapi wildcard star membaca dp[i][j-1] atau dp[i-1][j] .

SulitDynamic programming Rekursi

+10

Kamu mendapatkan string s dan pola p. Dalam pola, sebuah huruf cocok dengan huruf yang sama, titik . cocok dengan satu huruf apa pun, dan tanda bintang * berarti nol atau lebih salinan elemen tepat sebelumnya, yaitu huruf atau titik. Kembalikan true jika pola cocok dengan seluruh s, dan false jika tidak.

Fungsi

isMatch(s: string, p: string) → boolean

sstring: string yang dicocokkan, hanya huruf kecil
pstring: pola huruf, titik, dan tanda bintang
Mengembalikanboolean: true jika p cocok dengan semua s, false jika tidak

Batasan

1 ≤ s.length ≤ 1000
1 ≤ p.length ≤ 1000
s hanya berisi huruf kecil bahasa Inggris.
p hanya berisi huruf kecil bahasa Inggris, . dan *.
Setiap * mengikuti sebuah huruf atau ., jadi p tidak pernah diawali dengan * dan tidak pernah memiliki dua tanda bintang berturut-turut.

Contoh

Input: s = "moon"p = "mo*n"
Output: true
Penjelasan: o* mengambil kedua huruf o, jadi m, o*, dan n mengeja moon dengan tepat.

Input: s = "tree"p = "t.e"
Output: false
Penjelasan: t.e cocok dengan tre, awal dari tree, tetapi huruf e terakhir tersisa, dan kecocokan harus mencakup seluruh s.

Input: s = "sky"p = "z*s.*y"
Output: true
Penjelasan: z* mengambil nol salinan z, s cocok dengan s, .* mengambil k, dan y cocok dengan y.

Pertanyaan lanjutan

Bisakah kamu juga mendukung +, satu atau beberapa salinan elemen sebelumnya, dengan tabel yang sama?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Bintang dapat mencocokkan berapa pun jumlah salinan, dan jumlah yang tepat bergantung pada apa yang mengikutinya. Perlakukan sebuah huruf dan bintangnya sebagai satu unit dengan dua langkah: lewati unit itu, atau konsumsi satu huruf dan tetap di unit itu. Tabel yang mencatat awalan s mana yang cocok dengan awalan p mencoba setiap pilihan satu kali.

Cocokkan dari kiri dengan rekursi

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Bandingkan sufiks: match(i, j) menunjukkan apakah s[i:] cocok dengan p[j:]. Huruf atau titik tanpa tanda bintang harus cocok dengan s[i], dan sisanya juga harus cocok. Unit x* bisa mengambil nol salinan lalu dilewati, atau mengambil s[i] lalu tetap berada pada unit yang sama. Dengan begitu, satu tanda bintang bisa mengambil berapa pun banyaknya huruf. Kedua cabang mencakup semua pilihan yang dimiliki tanda bintang, jadi tidak ada kecocokan yang terlewat.

Setiap tanda bintang membagi pencarian menjadi dua. Untuk 30 huruf a dan sepuluh salinan a* yang diikuti huruf b, rekursi mencoba sekitar 8.5 × 10^8 cara membagi huruf di antara tanda-tanda bintang sebelum menjawab false, padahal hanya ada (n+1) × (m+1) pasangan (i, j) yang berbeda.

Algoritma

Tulis match(i, j) untuk sufiks yang dimulai pada i dan j.
Jika j melewati akhir p, kembalikan apakah i melewati akhir s.
Atur first berdasarkan apakah s[i] ada dan p[j] adalah s[i] atau titik.
Jika p[j+1] adalah bintang, kembalikan match(i, j+2) atau first and match(i+1, j).
Jika tidak, kembalikan first and match(i+1, j+1). Jawabannya adalah 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)

Isi tabel prefiks

Intuisi

Misalkan dp[i][j] menyatakan apakah i huruf pertama dari s cocok dengan j karakter pertama dari p. dp[0][0] bernilai true. Pada baris 0, string kosong hanya cocok dengan prefiks pola jika setiap elemennya diakhiri tanda bintang, seperti z* atau a*b*.

Huruf atau titik pada p[j-1] harus cocok dengan s[i-1], dan bagian sisanya harus cocok: sel diagonal, dp[i-1][j-1]. Tanda bintang dengan elemen x = p[j-2] memiliki dua langkah. Nol kemunculan menghapus x*: dp[i][j-2]. Satu kemunculan lagi, jika x cocok dengan s[i-1], membiarkan x* yang sama untuk mencocokkan string yang lebih pendek: dp[i-1][j], sel di atasnya. Setiap kemunculan bergerak satu langkah ke atas pada kolom tanda bintang. Untuk sky dan z*s.*y, kolom z*s.* bernilai true untuk s dengan nol kemunculan, lalu untuk sk dan sky bergerak satu langkah ke atas setiap kali.

Setiap sel membaca baris di atas atau sel di sebelah kirinya, jadi mengisi baris demi baris memastikan nilai-nilai tersebut sudah tersedia.

Algoritma

Buat tabel dp berisi (n+1) × (m+1) nilai false, lalu atur dp[0][0] menjadi true.
Untuk j dari 2 sampai m, atur dp[0][j] menjadi true jika p[j-1] adalah tanda bintang dan dp[0][j-2] bernilai true.
Untuk setiap sel dengan i ≥ 1 dan j ≥ 1, jika p[j-1] adalah tanda bintang, atur nilainya menjadi dp[i][j-2] atau (p[j-2] cocok dengan s[i-1] dan dp[i-1][j]).
Jika tidak, atur nilainya menjadi (p[j-1] cocok dengan s[i-1]) dan dp[i-1][j-1].
Kembalikan 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]

Sisakan hanya dua baris

Intuisi

Baris i hanya membaca dua sel dari baris i-1, yaitu sel diagonal dan sel di atasnya, serta selnya sendiri yang berjarak dua posisi ke kiri. Pertahankan dua array, prev dan cur, lalu tukar keduanya setelah setiap huruf dalam s: nol salinan adalah cur[j-2], satu salinan tambahan adalah prev[j], dan kecocokan biasa adalah prev[j-1]. Penggunaan memori turun dari sekitar 10^6 sel menjadi dua baris berisi 1001 sel. Kamu tidak dapat menukar input untuk memperpendek baris, karena string dan pola memiliki peran yang berbeda.

Algoritma

Isi prev dengan baris 0 tabel.
Untuk setiap huruf dalam s, atur cur[0] menjadi false dan isi cur[1..m] sesuai aturan tabel, dengan membaca prev untuk baris di atasnya.
Tukar prev dan cur.
Kembalikan 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]

Jebakan dan kasus tepi

Membiarkan star mengambil huruf sebanyak mungkin. a*a cocok dengan aaa, tetapi a* yang greedy memakan ketiga huruf dan a terakhir tidak cocok.
Membaca dp[i-1][j-2] untuk satu salinan lagi. Itu membuat star hanya bisa mengambil paling banyak satu huruf, jadi aa terhadap a* menghasilkan false.
Membiarkan baris 0 bernilai false setelah sel pertamanya. Lalu b terhadap a*b gagal, karena b memerlukan a* untuk cocok dengan prefiks kosong.
Membandingkan s[i-1] dengan star, bukan elemennya, p[j-2]. Lalu a terhadap a* gagal.
Tidak mengatur ulang cur[0] menjadi false dalam versi dua baris. Setelah pertukaran, nilainya bisa berisi true dari baris dasar, dan aab terhadap b menghasilkan true.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu Pencocokan Ekspresi Reguler?

Solusi tabel berjalan dalam waktu O(n × m) untuk string dengan panjang n dan pola dengan panjang m, karena setiap sel membaca paling banyak dua sel lainnya. Solusi ini membutuhkan memori O(n × m) untuk tabel lengkap, atau O(m) dengan dua baris. Rekursi biasa dapat membutuhkan waktu eksponensial untuk pola dengan banyak tanda bintang.

Apa bedanya dengan pencocokan wildcard?

Dalam pencocokan wildcard, seperti pada pola nama file, * berdiri sendiri dan cocok dengan rangkaian karakter apa pun, sedangkan ? cocok dengan satu karakter. Di sini, * hanya mengulang elemen sebelumnya, dan teks apa pun ditulis sebagai .*. Keduanya menggunakan tabel atas prefiks, tetapi wildcard star membaca dp[i][j-1] atau dp[i-1][j].

Mengapa tidak menggunakan library regex dari bahasa tersebut?

Pewawancara menginginkan algoritmanya, bukan pemanggilan library. Banyak mesin regex juga mencocokkan dengan backtracking, yaitu rekursi lambat dari pendekatan pertama, sehingga sepuluh salinan a* yang diikuti b dan dicocokkan dengan deretan panjang huruf a dapat membuatnya berjalan selama beberapa menit. Tabel selalu selesai dalam O(n × m).

def isMatch(s, p):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

s = "moon"
p = "mo*n"

Output yang diharapkan

true

Regular Expression Matching

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Cocokkan dari kiri dengan rekursi

Isi tabel prefiks

Sisakan hanya dua baris

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa