Regular Expression Matching

Q: Regular İfade Eşleştirmenin zaman karmaşıklığı nedir?

Tablo çözümü, n uzunluğunda bir dize ve m uzunluğunda bir desen için O(n × m) zamanda çalışır; çünkü her hücre en fazla iki başka hücreyi okur. Tablonun tamamı için O(n × m) bellek, iki satırla ise O(m) bellek gerekir. Basit özyineleme, çok sayıda yıldız içeren desenlerde üstel zaman alabilir.

ZorDinamik programlama Özyineleme

+10

Bir s dizesi ve bir p deseni veriliyor. Desende, bir harf aynı harfle eşleşir, bir nokta . herhangi bir harfle eşleşir ve yıldız *, hemen önündeki harf veya nokta olan öğenin sıfır veya daha fazla kopyası anlamına gelir. Desen, s dizgesinin tamamıyla eşleşiyorsa true, aksi hâlde false döndürün.

Fonksiyon

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

sstring: eşleştirilecek dizge, yalnızca küçük harfler
pstring: harfler, noktalar ve yıldızlardan oluşan desen
Döndürürboolean: p, s'nin tamamıyla eşleşiyorsa true, aksi takdirde false

Kısıtlar

1 ≤ s.length ≤ 1000
1 ≤ p.length ≤ 1000
s yalnızca küçük İngilizce harfler içerir.
p yalnızca küçük İngilizce harfler, . ve * içerir.
Her * bir harfi ya da bir . karakterini izler; bu nedenle p hiçbir zaman * ile başlamaz ve art arda iki yıldız içermez.

Örnekler

Girdi: s = "moon"p = "mo*n"
Çıktı: true
Açıklama: o* hem iki o harfini de alır, böylece m, o* ve n birlikte tam olarak moon yazar.

Girdi: s = "tree"p = "t.e"
Çıktı: false
Açıklama: t.e, tre'ye, yani tree'nin başlangıcına uyar; ancak son e açıkta kalır ve bir eşleşme s'nin tamamını kapsamalıdır.

Girdi: s = "sky"p = "z*s.*y"
Çıktı: true
Açıklama: z* z'den sıfır kopya alır, s, s ile eşleşir, .* k'yı alır ve y, y ile eşleşir.

Ek soru

Aynı tabloyla, önündeki öğenin bir veya daha fazla kopyasını eşleştiren + işlecini de destekleyebilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Yıldız herhangi bir sayıda kopya alabilir ve doğru sayı, ardından ne geldiğine bağlıdır. Bir harfi ve yıldızını iki hamleli tek bir birim olarak ele al: onu atla ya da bir harfi tüketip üzerinde kal. s öneklerinin p önekleriyle hangilerinin eşleştiğini gösteren bir tablo, her seçeneği bir kez dener.

Özyinelemeyle soldan eşleştir

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Sonekleri karşılaştır: match(i, j), s[i:] ifadesinin p[j:] ile eşleşip eşleşmediğini söyler. Yıldızsız bir harf veya nokta s[i] ile eşleşmeli, geri kalanı da eşleşmelidir. x* birimi ya sıfır kopya alıp atlanır ya da s[i] karakterini tüketip aynı birimde kalır; böylece tek bir yıldız istediği sayıda harfi alabilir. İki dal, yıldızın sahip olduğu tüm seçenekleri kapsar; dolayısıyla hiçbir eşleşme gözden kaçmaz.

Her yıldız aramayı ikiye böler. Otuz a harfi için, on adet a* ve ardından bir b olduğunda, özyineleme false yanıtını vermeden önce harfleri yıldızlar arasında paylaştırmanın yaklaşık 8.5 × 10^8 yolunu dener; oysa yalnızca (n+1) × (m+1) farklı (i, j) çifti vardır.

Algoritma

i ve j konumlarında başlayan sonekler için match(i, j) yazın.
j, p'nin sonunu geçmişse i'nin s'nin sonunu geçip geçmediğini döndürün.
first değerini, s[i]'nin var olup olmadığına ve p[j]'nin s[i] ya da bir nokta olup olmadığına göre ayarlayın.
p[j+1] bir yıldızsa match(i, j+2) veya first and match(i+1, j) sonucunu döndürün.
Aksi hâlde first and match(i+1, j+1) sonucunu döndürün. Yanıt match(0, 0) değeridir.

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)

Önekler tablosunu doldur

Sezgi

dp[i][j], s dizgesinin ilk i harfinin p dizgesinin ilk j karakteriyle eşleşip eşleşmediğini belirtir. dp[0][0] true'dur. 0. satırda boş dizge, bir desen önekiyle yalnızca içindeki her öğenin yıldızlı olması durumunda eşleşir; örneğin z* veya a*b*.

p[j-1] konumundaki bir harf veya nokta, s[i-1] ile eşleşmeli ve geri kalanı da eşleşmelidir: çapraz hücre, dp[i-1][j-1]. x = p[j-2] öğesine sahip bir yıldızın iki hamlesi vardır. Sıfır kopya, x* öğesini kaldırır: dp[i][j-2]. x, s[i-1] ile eşleştiğinde bir kopya daha, daha kısa dizgenin tamamlanması için aynı x* öğesini bırakır: üstteki hücre olan dp[i-1][j]. Her kopya, yıldızın sütununda bir adım yukarı çıkar. sky ve z*s.*y için, z*s.* sütunu sıfır kopyayla s için true olur; ardından sk ve sky için her seferinde bir adım yukarı çıkar.

Her hücre, üst satıra veya solundaki hücrelere bakar; bu nedenle satır satır doldurulduğunda gereken hücreler hazır olur.

Algoritma

(n+1) × (m+1) adet false değerinden oluşan bir dp tablosu oluştur ve dp[0][0] değerini true olarak ayarla.
j için 2'den m'ye kadar, p[j-1] bir yıldızsa ve dp[0][j-2] true ise dp[0][j] değerini true olarak ayarla.
i ≥ 1 ve j ≥ 1 olan her hücre için, p[j-1] bir yıldızsa hücreyi dp[i][j-2] veya (p[j-2], s[i-1] ile eşleşir ve dp[i-1][j]) olarak ayarla.
Aksi hâlde hücreyi (p[j-1], s[i-1] ile eşleşir) ve dp[i-1][j-1] olarak ayarla.
dp[n][m] değerini döndür.

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]

Yalnızca iki satır tutun

Sezgi

i satırı, i-1 satırındaki yalnızca iki hücreyi (köşegendeki ve üstündeki hücreyi) ve ayrıca kendi satırında iki hücre solundaki hücreyi okur. prev ve cur adında iki dizi tutun ve s dizgesinin her harfinden sonra bunları yer değiştirin: sıfır kopya cur[j-2], bir kopya daha prev[j], doğrudan eşleşme ise prev[j-1] olur. Bellek kullanımı yaklaşık 10^6 hücreden 1001 elemanlı iki satıra düşer. Satırları kısaltmak için girdilerin yerini değiştiremezsiniz; çünkü dizge ve desen farklı roller üstlenir.

Algoritma

prev değişkenini tablonun 0. satırıyla doldur.
s içindeki her harf için cur[0] değerini false olarak ayarla ve üst satır için prev değerini okuyarak cur[1..m] dizisini tablonun kurallarına göre doldur.
prev ve cur değerlerini yer değiştir.
prev[m] değerini döndür.

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]

Tuzaklar ve uç durumlar

Bir yıldızın mümkün olduğunca çok harf almasına izin vermek. a*a, aaa ile eşleşir; ancak açgözlü a* üç harfin tamamını tüketir ve son a eşleşmez.
Bir kopya daha için dp[i-1][j-2] değerini okumak. Bu, yıldızın en fazla bir harf almasına izin verir; bu yüzden aa ile a* karşılaştırmasının sonucu false olur.
İlk hücresinden sonra 0. satırı false bırakmak. Böylece b ile a*b eşleşmez; çünkü b'nin eşleşmesi için a*'ın boş önekle eşleşmesi gerekir.
s[i-1] değerini yıldızın elemanı p[j-2] yerine yıldızla karşılaştırmak. Bu durumda a ile a* eşleşmez.
İki satırlı sürümde cur[0] değerini false olarak sıfırlamamak. Takas işleminden sonra başlangıç satırındaki true değerini tutabilir ve aab ile b karşılaştırmasının sonucu true olur.

Sıkça sorulan sorular3

Regular İfade Eşleştirmenin zaman karmaşıklığı nedir?

Tablo çözümü, n uzunluğunda bir dize ve m uzunluğunda bir desen için O(n × m) zamanda çalışır; çünkü her hücre en fazla iki başka hücreyi okur. Tablonun tamamı için O(n × m) bellek, iki satırla ise O(m) bellek gerekir. Basit özyineleme, çok sayıda yıldız içeren desenlerde üstel zaman alabilir.

Bu, joker karakter eşleştirmesinden nasıl farklıdır?

Joker karakter eşleştirmesinde, dosya adı kalıplarında olduğu gibi, * tek başına durur ve herhangi bir karakter dizisiyle eşleşir; ? ise tek bir karakterle eşleşir. Burada * yalnızca kendisinden önceki öğeyi tekrarlar ve herhangi bir metin .* şeklindedir. Her ikisi de önekler üzerinde bir tablo kullanır, ancak joker karakter yıldızı dp[i][j-1] veya dp[i-1][j] değerini okur.

Neden dilin regex kütüphanesini kullanmıyorsunuz?

Görüşmeyi yapan kişi bir kütüphane çağrısını değil, algoritmayı görmek ister. Birçok regex motoru da geri izlemeyle eşleşme yapar; bu, ilk yaklaşımın yavaş yinelemesidir. Bu nedenle, uzun bir a dizisinin ardından gelen b ile eşleştirilen on adet a*, işlemin dakikalarca sürmesine yol açabilir. Tablo her zaman O(n × m) sürede tamamlanır.

def isMatch(s, p):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argümanlar

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

Beklenen Çıktı

true

Regular Expression Matching

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Özyinelemeyle soldan eşleştir

Önekler tablosunu doldur

Yalnızca iki satır tutun

Tuzaklar ve uç durumlar

Sıkça sorulan sorular3

Benzer problemler