Regular Expression Matching

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

Tablo çözümü O(n × m) zamanda çalışır; burada n , s uzunluğu ve m , p uzunluğudur; çü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. Düz özyineleme, çok sayıda yıldız içeren desenlerde üstel zaman alabilir.

Q: Yıldız hücresi neden çaprazdaki hücreyi değil, üstündeki hücreyi okuyor?

Yukarıdaki hücre olan dp[i-1][j] , s harfinin bir eksiğiyle aynı örüntüdür ve yıldız hâlâ içindedir. Yani yıldız s[i-1] harfini aldıktan sonra, s[i-2] harfini de alabilir ve sütun boyunca yukarı doğru böyle devam edebilir. Köşegen biçimindeki dp[i-1][j-2] hücresi, bir harften sonra yıldızı kaldırır; bu da herhangi sayıda kopya yerine tam olarak bir kopyaya izin verir.

ZorDinamik programlama Özyineleme

+10

Bir s dizgeniz ve bir p deseniniz var. Desende bir harf aynı harfle eşleşir, bir nokta . herhangi bir harfle eşleşir ve yıldız *, hemen önündeki öğenin (bir harf veya nokta) sıfır ya da daha fazla kez tekrarlanması anlamına gelir. Desen, s dizgesinin yalnızca bir bölümüyle değil, 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 dize, yalnızca küçük harfler
pstring: harflerin, noktaların ve yıldızların deseni
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 harfin veya . işaretinin ardından gelir; 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* iki o harfini de alır; böylece m, o* ve n birlikte tam olarak moon sözcüğünü oluşturur.

Girdi: s = "tree"p = "t.e"
Çıktı: false
Açıklama: t.e yalnızca üç harfli dizelerle eşleşir: t, herhangi bir harf, ardından e. tree sözcüğünün başındaki tre ile eşleşir, ancak son e artar ve eşleşme s dizgesinin tamamını kapsamalıdır.

Girdi: s = "sky"p = "z*s.*y"
Çıktı: true
Açıklama: z* sıfır tane z alır, s s ile eşleşir, .* k harfini alır ve y y ile eşleşir. Yıldızlı bir harf hiçbir şeyi temsil etmeyebilir, bu nedenle sky içinde hiç görünmeyen bir z hiçbir maliyete neden olmaz.

Gönderirken +29 gizli test

Ek soru

Öncesindeki öğenin bir veya daha fazla kopyasını, aynı tabloyla + için de destekleyebilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Bir yıldız herhangi sayıda kopya alabilir ve doğru sayı, ardından ne geldiğine bağlıdır. Mümkün olduğunca çok kopya almak işe yaramaz: aaa karşısında a*a deseni, a*'ın üç harfin tamamını yutmasına ve son a için hiçbir şey bırakmamasına izin verir. Bunu çözen fikir, bir harfi ve yıldızını iki hamlesi olan tek bir birim olarak ele almaktır: ya onu atla ya da bir harfi yutmasına ve bulunduğu yerde kalmasına izin ver. Bir tablo, s'nin her önekinin p'nin her önekiyle eşleşip eşleşmediğini kaydeder; böylece her seçenek bir kez denenir ve bu tablonun iki satırı yeterlidir.

Özyineleme kullanarak soldan eşleştirme

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

Sezgi

match(i, j) fonksiyonunun s[i:] son ekinin p[j:] son ekiyle eşleşip eşleşmediğini yanıtladığını varsayalım. Desen tükenmişse yalnızca dizge de tükenmişse eşleşir. Aksi hâlde first değerini hesaplayın: s[i] harfi vardır ve p[j] bu harf ya da bir noktadır.

Şimdi bir karakter ilerisine bakın. p[j+1] bir yıldızsa p[j]*, iki hamlesi olan tek bir birimdir. Sıfır kopya alabilir: match(i, j+2) ile her iki karakteri de atlayın. Ya da first doğruysa bir kopya alabilir: s[i] karakterini tüketin ve bir tane daha almaya hazır olmak için match(i+1, j) ile aynı birimde kalın. j konumunda kalmak, tek bir yıldızın her seferinde bir harf olmak üzere istediği sayıda harf almasını sağlar. Yıldız yoksa p[j] tam olarak bir harfle eşleşmelidir: first and match(i+1, j+1).

Yavaştır çünkü her yıldız aramayı ikiye böler ve başarısızlık çoğunlukla ancak en sonunda bulunur. On kopya a* ve ardından bir b içeren desenle, a harfinden oluşan 30 harfi ele alalım. Özyineleme, 30 a harfinin bir kısmını ya da tamamını on yıldız arasında paylaşmanın her yolunu dener; yaklaşık 8.5 × 10^8 yol vardır ve false yanıtını verebilmeden önce yaklaşık 2 × 10^9 çağrı yapar. Büyük testlerde 1000 harf vardır. Oysa yalnızca (n+1) × (m+1) farklı (i, j) çifti bulunur.

Algoritma

i ve j konumlarından başlayan son ekler için match(i, j) yazın.
j, p dizgesinin sonunu geçmişse i'nin s dizgesinin sonunu geçip geçmediğini döndürün.
first değerini, s[i]'nin mevcut olup olmadığına ve p[j]'nin s[i] veya 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) değerini döndürün.
Aksi hâlde first and match(i+1, j+1) değerini döndürün. Yanıt match(0, 0) olur.

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)

Bir önekler tablosunu doldurun

Sezgi

Durum. dp[i][j], s dizgesinin ilk i harfinin p dizgesinin ilk j karakteriyle eşleşip eşleşmediğini belirtir. 0 indisi boş bir öneki temsil eder.

Temel satır ve sütun. dp[0][0] doğrudur: boş bir desen, boş bir dizgeyle eşleşir. 0. sütunun altındaki değerler yanlıştır; çünkü boş bir desen bir harfle eşleşemez. 0. satır ise biraz inceliklidir: Bir desen öneki, yalnızca içindeki her öğe z* veya a*b* gibi yıldızlıysa boş dizgeyle eşleşir. Bu nedenle p[j-1] bir yıldız ve dp[0][j-2] doğru olduğunda dp[0][j] doğrudur.

Geçişler. p[j-1] bir harf veya nokta ise son harf s[i-1] ile eşleşmelidir ve geri kalanı da eşleşmelidir: köşegendeki dp[i-1][j-1]. p[j-1] bir yıldızsa yıldızın öğesi x = p[j-2] olur ve yıldızın iki seçeneği vardır. Sıfır kopya: desenden x* öğesini çıkar, yani iki hücre soldaki dp[i][j-2] değerini kullan. Bir kopya daha: x, s[i-1] ile eşleşiyorsa bu harf kopyalardan biridir ve aynı x* yine de daha kısa dizgeyi eşleştirmelidir; bu nedenle aynı sütunda, hemen üstteki hücre olan dp[i-1][j] değerine bak. Her kopya o sütunda bir adım yukarı çıkmak demektir; tek bir yıldızın herhangi sayıda harfi kapsamasını sağlayan da budur.

sky ve z*s.*y için tablo aşağıdadır. Sütunlar "", z, z*, z*s, z*s., z*s.*, z*s.*y öneklerini gösterir (T doğru, F yanlış). "" satırı [T, F, T, F, F, F, F] şeklindedir: yalnızca z* boş olabilir. s satırı [F, F, F, T, F, T, F] şeklindedir: s, köşegendeki üst hücrede z* boşken s ile eşleşir ve ardından .* sıfır kopya alır. sk satırı [F, F, F, F, T, T, F] şeklindedir: z*s.* için olan hücre, bir kopya daha seçeneğiyle doğru değerini alır; nokta k harfini eşleştirir ve hemen üstündeki T değerinden okunur. sky satırı [F, F, F, F, F, T, T] şeklindedir: nokta yıldızı aynı şekilde y harfini eşleştirerek sütunda bir adım daha yukarı çıkar, ardından y köşegende y ile eşleşir. Son hücre doğrudur.

Her hücre, üst satırdaki veya solundaki hücreleri okur; bu nedenle satır satır, soldan sağa doldurulduğunda gerekli değerler hazır olur. Toplam (n+1) × (m+1) hücre vardır; en büyük testlerde bu yaklaşık 10^6 hücre eder ve her biri için sabit miktarda işlem yapılır.

Algoritma

(n+1) × (m+1) adet false değerden oluşan bir dp tablosu oluşturun ve dp[0][0] değerini true olarak ayarlayın.
2'den m'ye kadar j için, p[j-1] bir yıldızsa ve dp[0][j-2] true ise dp[0][j] değerini true olarak ayarlayın.
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şiyorsa ve dp[i-1][j]) olarak ayarlayın.
Aksi takdirde hücreyi (p[j-1], s[i-1] ile eşleşiyorsa) ve dp[i-1][j-1] olarak ayarlayın.
dp[n][m] değerini döndürün.

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 tut

Sezgi

i satırı, i-1 satırındaki iki hücreyi (çaprazdaki ve üstündeki hücreyi) ve kendi satırındaki, iki hücre solundaki bir hücreyi okur. Daha yukarıdaki satırlar bir daha okunmaz. İki dizi tut: tamamlanmış satır için prev, doldurmakta olduğun satır için cur; s içindeki her harften sonra bunları yer değiştir. Geçişler aynı kalır: sıfır kopya cur[j-2], bir kopya daha prev[j], normal eşleşme prev[j-1].

prev dizisini boş dizenin temel satırı olarak başlat. Her satırın başında cur[0] değerini false yap: yer değiştirme sonrasında cur eski bir satırı tutar ve temel satırın ilk girdisi true'dur.

Her satırda m + 1 girdi bulunur; böylece bellek kullanımı yaklaşık 10^6 hücreden 1001 elemanlı iki satıra düşer. Düzenleme uzaklığından farklı olarak, satırları kısaltmak için iki girdinin yerini değiştiremezsin; çünkü dizenin ve desenin rolleri farklıdır.

Algoritma

prev değişkenini taban satırla doldurun: 0 konumunda true, p[j-1] yıldız olduğunda ve prev[j-2] true olduğunda j konumunda true.
s dizisinin her harfi için cur[0] değerini false olarak ayarlayın.
cur[1..m] değerlerini doldurun: yıldız hücresinin değeri cur[j-2] veya (öğe eşleşiyor ve prev[j]); diğer hücrelerin değeri (eşleşiyor) ve prev[j-1].
prev ile cur değişkenlerini yer değiştirin.
prev[m] değerini döndürün.

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

Yanlış cevapların çoğu yıldızdan kaynaklanır: neyi tekrarladığı, bunu kaç kez yaptığı ve hiçbir şeyle eşleşip eşleşemediği.

Yıldızın alabildiği kadar çok harf almasına izin vermek. a*a, aaa ile eşleşir; ancak açgözlü bir 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, a* ile eşleştirildiğinde sonuç false olur. Yıldızın sütununda kal: dp[i-1][j].
İlk hücre dışında 0. satırdaki tüm hücreleri false bırakmak. O zaman b, a*b ile eşleşemez; çünkü b'den önceki boş önekle eşleşmesi için a* gerekir.
s[i-1] değerini yıldızın kendisiyle değil, yıldızın öğesi olan p[j-2] ile karşılaştırmak.
* karakterini dosya adı kalıplarındaki gibi "herhangi bir metin" olarak değerlendirmek. Burada yalnızca önündeki öğeyi tekrarlar; herhangi bir metin için .* kullanılır.
Kısmi eşleşmeyi kabul etmek. t.e, tree sözcüğünün başlangıcıyla eşleşir; ancak geride bir harf kaldığı için cevap false olur.
İki satırlı sürümde cur[0] = false atamasını unutmak. İlk takastan sonra cur[0], temel satırdaki true değerini tutar.

Sıkça sorulan sorular4

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

Tablo çözümü O(n × m) zamanda çalışır; burada n, s uzunluğu ve m, p uzunluğudur; çü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. Düz özyineleme, çok sayıda yıldız içeren desenlerde üstel zaman alabilir.

Yıldız hücresi neden çaprazdaki hücreyi değil, üstündeki hücreyi okuyor?

Yukarıdaki hücre olan dp[i-1][j], s harfinin bir eksiğiyle aynı örüntüdür ve yıldız hâlâ içindedir. Yani yıldız s[i-1] harfini aldıktan sonra, s[i-2] harfini de alabilir ve sütun boyunca yukarı doğru böyle devam edebilir. Köşegen biçimindeki dp[i-1][j-2] hücresi, bir harften sonra yıldızı kaldırır; bu da herhangi sayıda kopya yerine tam olarak bir kopyaya izin verir.

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

Dosya adı kalıplarında olduğu gibi joker karakter eşleştirmede de * tek başına kullanılır 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 metinle eşleşen kalıp .* şeklindedir. Her ikisi de önekler üzerinde bir tablo kullanılarak çözülür, ancak yıldız geçişi farklıdır: joker karakter eşleştirme dp[i][j-1] veya dp[i-1][j] değerlerini okur.

Dilin regex kütüphanesini neden kullanmıyorsun?

Bir mülakatı yapan kişi bir kütüphane çağrısı değil, algoritma ister. Ayrıca gerçek bir risk de vardır: birçok regex motoru geri izleme yoluyla eşleşir; bu, ilk yaklaşımdaki yavaş özyinelemedir. Uzun bir a harfleri dizisine karşı, ardından b gelen on adet a* kopyası gibi bir desen, böyle bir motorun dakikalarca çalışmasına neden olabilir. Tablo her zaman O(n × m) sürede tamamlanır.

Python

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

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

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

Beklenen

true

Regular Expression Matching

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Özyineleme kullanarak soldan eşleştirme

Bir önekler tablosunu doldurun

Yalnızca iki satır tut

Tuzaklar ve uç durumlar

Sıkça sorulan sorular4

Benzer problemler