Longest Valid Parentheses

Q: En Uzun Geçerli Parantezler için dinamik programlama çözümü var mı?

Evet. end[i] , i indeksinde biten en uzun düzgün biçimlendirilmiş alt dizenin uzunluğu olsun; s[i] değeri ( olduğunda bu değer 0'dır. s[i-1] değeri ( ise end[i] = end[i-2] + 2 olur. Değer ) ise, i-1 indeksinde biten dizinin öncesindeki karakter olan j = i - end[i-1] - 1 değerine bakın: s[j] değeri ( olduğunda bu karakter diziyi çevreler ve end[i] = end[i-1] + 2 + end[j-1] olur; son terim, solunda ona bitişik olan diziyi birleştirir. Yanıt, O(n) zaman ve bellek karmaşıklığında, en büyük end[i] değeridir.

ZorYığın Dinamik programlama

+10

Yalnızca ( ve ) karakterlerinden oluşan bir s dizgeniz var. Düzgün biçimlenmiş en uzun alt dizgeyi (ardışık karakterlerden oluşan bir bölümü) bulun: İçindeki her (, yine bu dizge içindeki daha sonraki bir ) ile kapatılmalı ve parantez çiftleri (()()) örneğindeki gibi doğru şekilde iç içe geçmelidir. Bu alt dizgenin uzunluğunu döndürün; () bile yoksa 0 döndürün.

Fonksiyon

longestValidParentheses(s: string) → integer

sstring: ( ve ) karakterlerinden oluşan bir dize
Döndürürinteger: en uzun düzgün biçimlendirilmiş alt dizenin uzunluğu ya da yoksa 0

Kısıtlar

1 ≤ s.length ≤ 6 × 10⁴
<|?

Örnekler

Girdi: s = "()(())"
Çıktı: 6
Açıklama: Dizgenin tamamı düzgün biçimlendirilmiştir: () ve ardından (()). Yan yana duran iki düzgün biçimlendirilmiş parça, tek bir düzgün biçimlendirilmiş parça oluşturur; dolayısıyla yanıt 6 karakterin tamamıdır.

Girdi: s = "())((())"
Çıktı: 4
Açıklama: 2. indeksteki ) eşleştiği bir paranteze sahip değildir; bu yüzden hiçbir yanıt onun üzerinden geçemez ve 3. indeksteki ( hiç kapatılmaz. En uzun parça, 4. indeksten 7. indekse kadar olan (()) parçasıdır; uzunluğu 4'tür ve baştaki () parçasından daha uzundur.

Girdi: s = "))(("
Çıktı: 0
Açıklama: Her iki ) de her iki ( işaretinden önce gelir, bu nedenle hiçbir ( asla kapatılmaz. Hiçbir alt dize doğru biçimlendirilmemiştir ve yanıt 0'dır.

Ek soru

En uzun düzgün biçimlendirilmiş alt dizenin nerede başladığını da bildirebilir misin? Birden fazla alt dizenin uzunluğu aynıysa en soldakini seç.

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Bunu zorlaştıran iki şey vardır. Doğru biçimlendirilmiş parçalar birbirine değdiğinde birleşir; bu nedenle yan yana duran () ve (()), 6 uzunluğunda tek bir dizi sayılır. ())(()) içindeki ) gibi fazladan bir karakter ise diziyi böler; böylece hiçbir yanıt bu karakterin ötesine geçemez. Her başlangıç konumunu denemek O(n²) maliyetlidir. Çözüm, geçerli dizinin nerede başladığını hatırlamaktır: tabanda bir temel işaretçisi bulunan bir indeks yığını bunu tek geçişte yapar; basit sayaçlarla yapılan iki geçiş ise hiç yığın kullanmadan aynı işi yapar.

Her başlangıçtan bir alt dize oluşturun

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

Sezgi

Bir alt dizeyi soldan sağa okurken, ( için 1 ekleyen ve ) için 1 çıkaran bir denge değeri tut. Alt dize, denge değeri hiçbir zaman 0'ın altına düşmüyorsa ve sonunda 0 oluyorsa düzgün biçimlidir. 0'ın altına düşmesi, açıkta kapatılacak bir şey yokken bir ) geldiği anlamına gelir.

Öyleyse bir başlangıç noktası belirle ve sağa doğru ilerleyerek denge değerini her seferinde bir karakter için güncelle. Değer her 0'a döndüğünde, başlangıç noktasından buraya kadar olan kısım düzgün biçimlidir ve uzunluğunu kaydedersin. Değer 0'ın altına düştüğü anda dur: bu ), bu başlangıç noktasından itibaren daha uzun olan her kısımda eşleşmeden kalır. Her düzgün biçimli alt dizenin bir başlangıç noktası vardır ve onun için her bitiş noktasını denersin; dolayısıyla hiçbirini kaçırmazsın.

Sorun, maliyettir. ( karakterinden 59998 tane ve ardından () içeren bir dizgede denge değeri hiçbir zaman 0'ın altına düşmez; bu yüzden her başlangıç noktası dizgenin sonuna kadar ilerler: n = 6 × 10^4 için yaklaşık n²/2 = 1.8 × 10^9 adım. Büyük testler bu şekilde oluşturulmuştur. (Her alt dizeyi baştan kontrol etmek, onu büyüterek kontrol etmekten daha da kötü olurdu: O(n³).)

Algoritma

best değerini 0 olarak ayarla.
Her başlangıç için balance değerini 0 olarak ayarla ve bitişi başlangıçtan son karaktere kadar ilerlet.
( için 1 ekle ve ) için 1 çıkar.
balance 0'ın altındaysa bu başlangıç için işlemi durdur. 0 ise, end - start + 1 uzunluğundaki aralıkla best değerini güncelle.
best değerini döndür.

def longestValidParentheses(s):
    best = 0
    for start in range(len(s)):
        balance = 0
        for end in range(start, len(s)):
            balance += 1 if s[end] == "(" else -1
            if balance < 0:
                # A ')' without a partner: no longer run starts here
                break
            if balance == 0:
                best = max(best, end - start + 1)
    return best

Taban işaretçisi olan indeks yığını

Sezgi

Yığınla eşleşen parantezleri bulma yöntemi tanıdıktır: her ( için yığına ekleme yapar, her ) için bir öğe çıkarırsın. Burada uzunluklara da ihtiyacın olduğundan, indisleri yığına ekle ve yığının altına fazladan bir indis koy: bulunduğun dizinin hemen öncesindeki konum olan taban. Başlangıçta henüz hiçbir şey okunmadığından taban -1'dir.

( için indisini yığına ekle. ) için bir öğe çıkar. İki şey olabilir. Yığın artık boşsa tabanı çıkarmışsındır; yani bu ) karakterinin kapatacağı bir parantez yoktur. Düzgün biçimlendirilmiş hiçbir alt dize bunu içeremez ve bu karakter yeni taban olur: indisini yığına ekle. Aksi hâlde, üstte kalan indis, i konumunda biten dizinin son karakterinden önceki karakterin indisidir: ya hâlâ açık olan bir ( ya da taban. Ondan i konumuna kadar olan her şey eşleşmiştir ve dizi daha sola uzanamaz; bu nedenle uzunluğu i - top olur.

İşte ())((()) için adımlar:

i = 0, (: 0'ı yığına ekle. Yığın [-1, 0].
i = 1, ): 0'ı çıkar. Üstte -1 var, dolayısıyla dizi uzunluğu 1 - (-1) = 2.
i = 2, ): -1'i çıkar ve yığın boşalır. Bu ) karakterinin eşleşeni yoktur; bu yüzden yeni taban olarak 2'yi yığına ekle. Yığın [2].
i = 3, 4, 5, üç (: bunları yığına ekle. Yığın [2, 3, 4, 5].
i = 6, ): 5'i çıkar. Üstte 4 var, dolayısıyla dizi uzunluğu 6 - 4 = 2.
i = 7, ): 4'ü çıkar. Üstte 3 var, dolayısıyla dizi uzunluğu 7 - 3 = 4; yanıt budur.

Birbirine bitişik parçaların birleşmesini sağlayan tabandır. ()(()) için ilk çift 1 - (-1) = 2 uzunluğunu verir ve son ), 2 indisini çıkarıp üstte yine -1'i bulur; böylece 5 - (-1) = 6 uzunluğunu verir. Bunun yerine uzunluğu eşleşen ( karakterinden itibaren ölçmek 4 sonucunu verir ve baştaki () parçasını hesaba katmaz. Her indis en fazla bir kez yığına eklenip çıkarıldığından, bu geçiş O(n) zaman alır ve yığın en fazla n+1 indis tutabilir.

Algoritma

-1 tutan bir yığın başlatın ve best değerini 0 olarak ayarlayın.
Her i indeksi için, s[i] ( ise i değerini yığına ekleyin.
) ise bir kez yığından çıkarın.
Yığın şimdi boşsa, yeni taban olarak i değerini ekleyin. Aksi hâlde best değerini i - top ile güncelleyin.
best değerini döndürün.

def longestValidParentheses(s):
    # The bottom of the stack is the index just before the current run
    stack = [-1]
    best = 0
    for i, ch in enumerate(s):
        if ch == "(":
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                # This ')' has no partner: it becomes the new base
                stack.append(i)
            else:
                best = max(best, i - stack[-1])
    return best

İki geçişte açılışları ve kapanışları say

Sezgi

Yığın yalnızca geçerli aralığın nerede başladığını söyler. Bunu iki sayaç da yapabilir. Soldan sağa ilerleyerek son sıfırlamadan beri opens ve closes sayılarını say. Eşit olduklarında, sıfırlamadan beri gelen her şey doğru biçimlenmiştir ve uzunluğu 2 × closes olur. closes öne geçtiğinde, bir ) eşleşmemiştir; yığının tabanını kaybettiği an da aynıdır, bu yüzden iki sayacı da 0'a sıfırla.

Tek geçiş yeterli değildir. Hiç kapanmayan bir (, opens sayısını sürekli önde tutar ve sayaçlar bir daha eşitlenmez. (() üzerinde soldan geçiş, 2 açma ve 1 kapamayla biter ve hiçbir şey bulamaz; oysa () hemen yanı başındadır. Bu yüzden ikinci kez, rolleri değiştirerek sağdan sola ilerle: opens öne geçtiğinde sıfırla. Tersten okunduğunda (() önce bir kapama, ardından bir açma verir (eşit: uzunluk 2), sonra da sıfırlamaya neden olan bir açma verir. Yanıt, iki geçişten elde edilen büyük değerdir.

İki geçişin her aralığı nasıl yakaladığını açıklayalım: en uzun aralığın sınırları, asla eşleşemeyecek karakterlerle veya dizenin uçlarıyla çizilir. Sol sınırı başıboş bir ) ya da dizenin başlangıcıysa, soldan geçiş aralığın başladığı yerde sıfırlar ve bittiği yerde sayaçların eşitlendiğini görür. Sol sınırı başıboş bir ( ise sağ sınır ) olamaz; çünkü bu ), başıboş ('i kapatır ve aralık daha uzun olurdu. Dolayısıyla sağ sınır başıboş bir (</code) ya da dizenin sonudur ve sağdan geçiş aralığı aynı şekilde yakalar. Her geçiş dizeyi iki tam sayı kullanarak bir kez okur; bu nedenle zaman karmaşıklığı <code>O(n), ek bellek kullanımı ise O(1)'dir.

Algoritma

best değerini 0, opens ve closes değerlerini 0 olarak ayarla.
Soldan sağa ilerleyerek her karakteri say. Sayaçlar eşit olduğunda best değerini 2 × closes ile güncelle. closes daha büyük olduğunda ikisini de 0'a sıfırla.
Her iki sayacı da sıfırla, ardından aynı şekilde sağdan sola ilerle; ancak opens daha büyük olduğunda sıfırla.
best değerini döndür.

def longestValidParentheses(s):
    best = 0

    # Left to right: more ')' than '(' ends every run that started earlier
    opens = closes = 0
    for ch in s:
        if ch == "(":
            opens += 1
        else:
            closes += 1
        if opens == closes:
            best = max(best, 2 * closes)
        elif closes > opens:
            opens = closes = 0

    # Right to left: catches the runs that an unmatched '(' hid from the first pass
    opens = closes = 0
    for ch in reversed(s):
        if ch == "(":
            opens += 1
        else:
            closes += 1
        if opens == closes:
            best = max(best, 2 * opens)
        elif opens > closes:
            opens = closes = 0

    return best

Tuzaklar ve uç durumlar

Çoğu yanlış yanıt, doğru çiftleri yanlış yerlerde sayar ya da bir dizinin başlangıcını kaybeder.

Eşleşen çiftleri tüm dizgede saymak. ())((()) 3 çift içerir, ancak bunların hepsi bitişik değildir ve yanıt 6 değil, 4'tür.
Bir diziyi eşleşen ( konumundan ölçmek. ()(()) içinde son ), 2. indeksle eşleşir; bu da 4 verir ve önündeki () kısmını gözden kaçırır. Diziyi, çıkarma işleminden sonra yığında kalan indeksten ölçün.
Boş bir yığınla başlamak. Böylece ()) ifadesindeki ilk ) için karşılaştırılacak bir şey olmaz ve eşleşmeyen bir ), boş bir yığından öğe çıkarır. -1 taban değeri bu iki sorunu da çözer.
Sayaçları yalnızca tek yönde çalıştırmak. (() soldan sağa 0 döndürür, ()) ise sağdan sola 0 döndürür; her ikisinin de yanıtı 2'dir.
Sayaçlar eşit olduğunda sıfırlamak. Eşit sayımlar, ()() örneğinde olduğu gibi dizinin büyümeye devam edebileceği anlamına gelir; yalnızca taraflardan biri öne geçtiğinde sıfırlayın.
Lua ve R'de konumlar 1'den başlar; bu nedenle ilk taban değeri -1 değil, 0'dır.

Sıkça sorulan sorular3

Longest Valid Parentheses algoritmasının zaman karmaşıklığı nedir?

Hem yığın çözümü hem de iki geçişli sayaç çözümü her karakteri sabit sayıda okur; bu nedenle O(n) zamanda çalışırlar. Örneğin yalnızca ( karakterlerinden oluşan bir dizede yığın, en kötü durumda O(n) bellek gerektirirken sayaçlar O(1) bellek gerektirir. Her başlangıç konumunu denemek O(n²) zaman alır.

Neden yığın -1 ile başlıyor?

Ardışık dizinin uzunluğu, geçerli indeks ile diziden hemen önceki indeksin farkıdır. 0 indeksinde başlayan bir dizi için bu önceki indeks, dizenin bir adım öncesindeki -1 değeridir. Önce -1 değerini yığına eklemek, eşleşen bir ) ölçüm yaptığında yığının hiçbir zaman boş olmamasını sağlar; eşleşmeyen bir ) bu değeri yığından çıkardığında ise yeni taban olarak o ) geçer.

En Uzun Geçerli Parantezler için dinamik programlama çözümü var mı?

Evet. end[i], i indeksinde biten en uzun düzgün biçimlendirilmiş alt dizenin uzunluğu olsun; s[i] değeri ( olduğunda bu değer 0'dır. s[i-1] değeri ( ise end[i] = end[i-2] + 2 olur. Değer ) ise, i-1 indeksinde biten dizinin öncesindeki karakter olan j = i - end[i-1] - 1 değerine bakın: s[j] değeri ( olduğunda bu karakter diziyi çevreler ve end[i] = end[i-1] + 2 + end[j-1] olur; son terim, solunda ona bitişik olan diziyi birleştirir. Yanıt, O(n) zaman ve bellek karmaşıklığında, en büyük end[i] değeridir.

def longestValidParentheses(s):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argüman

s = "()(())"

Beklenen Çıktı

Longest Valid Parentheses

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Her başlangıçtan bir alt dize oluşturun

Taban işaretçisi olan indeks yığını

İki geçişte açılışları ve kapanışları say

Tuzaklar ve uç durumlar

Sıkça sorulan sorular3

Benzer problemler