Generate Parentheses

Q: Generate Parentheses algoritmasının zaman karmaşıklığı nedir?

Geri izleme çözümü, C(n) = (2n)! / ((n+1)! n!) Catalan sayısı kadar dize üretir; bu sayı 4^n / (n^1.5 √π) gibi büyür. Her dizenin uzunluğu 2n olur ve arama hiçbir dalı boşa harcamaz; bu nedenle toplam süre O(4^n / √n) olur. Ek alan, geçerli dize ve çağrı yığını için O(n) kadardır; çıktının kullandığı alan buna dahil değildir.

Q: n çift için kaç geçerli parantez dizgesi vardır?

Tam olarak n’inci Catalan sayısı: n 1’den 8’e kadar olduğunda 1, 2, 5, 14, 42, 132, 429 ve 1.430. Bunu görmenin bir yolu: Her düzgün biçimlenmiş dize ( + A + ) + B biçimindedir; burada ilk ( , o ) ile eşleşir ve A ile B, aralarında toplam n-1 çift bulunan düzgün biçimlenmiş dizelerdir. A’nın boyutu üzerinden toplama yapmak Catalan bağıntısını verir.

Q: closed < opened neden geçerli bir dizeyi garanti eder?

Bir dize, tam olarak eşleşmemiş bir ( olmadan bir ) geldiğinde bozulur; bu da ) sayısının ( sayısını aşacağı zamandır. ) karakterine yalnızca closed < opened iken izin vermek bunun olmasını engeller; ( karakterine yalnızca opened < n iken izin vermek ise her iki sayının da 2n uzunluğunda n 'e ulaşmasını sağlar. Bu iki kural birlikte, düzgün biçimlendirilmiş bir dizenin her önekini tanımlar.

Q: Generate Parentheses problemi özyineleme kullanılmadan çözülebilir mi?

Evet. Her biri iki sayacını içeren bir dize olan kısmi durumları bir yığında tut ve her durumu aynı iki kuralla genişlet. ) uzantısını ( uzantısından önce yığına eklersen, önce ( olan çıkar ve çıktı sıralı kalır. Yapılan iş aynıdır; kayıt tutma işi çağrı yığınından kendi yığınına taşınır.

OrtaGeri izleme Özyineleme

+10

Parantezlerden oluşan bir dizi, soldan sağa okunduğunda ) sayısı hiçbir zaman ( sayısını geçmiyorsa ve sonunda iki sayı eşitse düzgün biçimlenmiştir. Bu nedenle (())() düzgün biçimlenmiştir, ancak ())( değildir: üçüncü karakteri, hiç açılmamış bir çifti kapatır.

Bir n tamsayısı veriliyor. n açılış ve n kapanış parantezinden oluşan, sözlük sırasına göre sıralanmış tüm düzgün biçimlenmiş dizeleri döndür. Sözlük sıralamasında (, ) karakterinden önce gelir.

Fonksiyon

generateParenthesis(n: integer) → string-array

ninteger: parantez çiftlerinin sayısı
Döndürürstring-array: n çift parantez içeren her düzgün biçimli dizge, sözlük sırasına göre

Kısıtlar

1 ≤ n ≤ 8
n = 8 için cevap 1.430 dize içerir.

Örnekler

Girdi: n = 3
Çıktı: ["((()))", "(()())", "(())()", "()(())", "()()()"]
Açıklama: Üç çift, doğru biçimlendirilmiş beş şekilde düzenlenebilir. ((())), herhangi birini kapatmadan önce üçünü de açar ve ( sıralamada önce geldiğinden listenin başında yer alır; ()()() ise her çifti hemen kapatır ve listenin sonunda yer alır.

Girdi: n = 1
Çıktı: ["()"]
Açıklama: Bir parantez çiftinin düzgün biçimlenmiş tek bir dizilişi vardır. Bir ( ve bir ) içeren diğer tek dize )( şeklindedir; burada herhangi bir şey açılmadan kapanır.

Gönderirken +10 gizli test

Ek soru

İyi biçimlendirilmiş n çift dizgeleri üretmeden sayabilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Uzunluğu 2n olan dizelerin yalnızca küçük bir kısmı düzgün biçimlendirilmiştir: n = 3 için 64 dizenin 5'i, n = 8 içinse 65.536 dizenin 1.430'u. Bu işi çözen fikir, dizeyi soldan sağa oluşturmak ve yalnızca onu geçerli tutan karakterleri eklemektir; böylece arama hiçbir zaman tamamlanamayacak bir dala girmez. Neye izin verildiğini iki sayaç belirler: kaç tane ( yerleştirdiğiniz ve kaç tane ) yerleştirdiğiniz. Her adımda ) yerine önce ( denemek, dizelerin zaten sıralanmış olarak ortaya çıkmasını sağlar.

Her dizgeyi oluştur, ardından kontrol et

Sezgi

Doğrudan yöntem, 2n konumun her birini mümkün olan tüm şekillerde doldurup düzgün biçimlenmiş dizeleri tutmaktır. Her konumda ( veya ) bulunur; dolayısıyla 2^(2n) = 4^n dize vardır. Özyinelemeli bir işlev, sıradaki konuma ( yerleştirir ve özyinelemeli olarak devam eder; ardından oraya ) yerleştirip yeniden özyinelemeli olarak devam eder ve tamamlanan her dize bir kontrolden geçer.

Kontrol, dengeyi izleyerek dize boyunca ilerler: ( için 1 ekler, ) için 1 çıkarır. Denge hiçbir zaman 0'ın altına düşmez ve 0'da biterse dize düzgün biçimlenmiştir. Dengenin 0'ın altına düşmesi, ())( dizesinin üçüncü karakterinde olduğu gibi, kapatılacak açık bir parantez olmadan ) ile karşılaşıldığı anlamına gelir.

Her konumda ) öncesinde ( denenirse, ( ) işaretinden önce sıralandığı için dizeler sözlük sırasıyla listelenir. Böylece tutulan dizeler zaten sıralı olur.

Maliyet, her biri O(n) sürede kontrol edilen 4^n dizedir. n = 8 için 1.430 yanıt karşılığında 65.536 dize söz konusudur; yani işin yaklaşık %98'i boşa gider. Burada işlem tamamlanır çünkü n en fazla 8'dir; ancak her ek parantez çiftiyle iş yükü dört katına çıkar ve ilk karakter bunları zaten elerken, ) ile başlayan dizeler oluşturmaya devam eder.

Algoritma

2n karakterlik bir tampon ve yanıtlar için bir liste tutun.
fill(pos) fonksiyonunu yazın. pos, 2n'e eşitse tamponu kontrol edin ve düzgün biçimlendirilmişse kaydedin.
Aksi takdirde pos konumuna ( koyun ve fill(pos + 1) fonksiyonunu çağırın; ardından oraya ) koyun ve fonksiyonu tekrar çağırın.
Bir dizgeyi kontrol etmek için her ( için 1 ekleyin ve her ) için 1 çıkarın. Denge 0'ın altına düşer düşmez veya 0'da bitmezse dizgeyi reddedin.
fill(0) fonksiyonunu çağırın ve önceden sıralanmış dizgeleri döndürün.

def generateParenthesis(n):
    result = []
    path = []

    def is_balanced(text):
        balance = 0
        for ch in text:
            balance += 1 if ch == "(" else -1
            if balance < 0:
                return False  # a ")" with nothing open to close
        return balance == 0

    def fill():
        if len(path) == 2 * n:
            text = "".join(path)
            if is_balanced(text):
                result.append(text)
            return
        for ch in "()":  # "(" first keeps the output sorted
            path.append(ch)
            fill()
            path.pop()

    fill()
    return result

Açık ve kapalı sayımlarında geri izleme yapın

Sezgi

Kontrolü kurma işleminin içine taşı. Bir önek, tam olarak iki koşul sağlandığında hâlâ düzgün biçimlendirilmiş bir diziye tamamlanabilir: en fazla n açılış parantezi kullanır ve hiçbir zaman ) sayısı ( sayısından fazla olmaz. Dolayısıyla her adımda opened < n iken (, closed < opened iken de ) ekleyebilirsin. Dizi 2n uzunluğuna ulaştığında her iki sayı da n olur ve dizi düzgün biçimlendirilmiştir; artık kontrol edilecek başka bir şey kalmaz.

n = 2 için ağacın tamamı şöyledir. Boş diziden yalnızca ( eklenebilir, çünkü henüz hiçbir parantez açılmamıştır. ( durumundan her iki karakter de eklenebilir. (( dalında opened zaten 2 olduğundan yalnızca ) uygundur; bu iki kez eklenerek (()) elde edilir. () dalında hiçbir parantez açık olmadığından yalnızca ( uygundur, ardından ) gelir ve ()() elde edilir. Her dal bir yanıtta sonlanır: arama, atmak zorunda kalacağı bir dizi oluşturmaz.

Hiçbir yanıt atlanmaz. Düzgün biçimlendirilmiş bir dizinin her öneki iki kurala da uyar; bu nedenle arama, dizinin sıradaki ihtiyacı olan karakteri hiçbir zaman reddetmez ve her dizi, karakterleri ağaçta tek bir yolu belirlediği için yalnızca bir kez üretilir. Sıralama ilk yaklaşımdaki gibi çalışır: iki dizi, yollarının ayrıldığı noktada ilk kez farklılaşır ve burada önce ( dalı incelenir.

Her yaprak bir yanıttır ve n çift için yanıt sayısı, 4^n / (n^1.5 √π) gibi büyüyen Catalan sayısı C(n)'dir. Her iç düğüm en az bir yaprağa giden yol üzerinde yer alır; bu nedenle yanıt başına en fazla 2n iç düğüm bulunur ve bir yanıtı kopyalamak O(n) maliyetlidir. Toplam maliyet O(n × C(n)) = O(4^n / √n) olur: n = 8 için 65,536 diziyi kontrol etmek yerine doğrudan 1,430 dizi oluşturulur.

Algoritma

Oluşturulan dizgeyi ve ikisi de 0 olan opened ve closed sayaçlarını tutun.
Dizgenin uzunluğu 2n ise bir kopyasını kaydedin ve geri dönün.
opened < n ise ( ekleyin, opened + 1 ile özyinelemeli çağrı yapın ve onu kaldırın.
closed < opened ise ) ekleyin, closed + 1 ile özyinelemeli çağrı yapın ve onu kaldırın.
Boş dizgeden başlayın ve kaydedilen dizgeleri döndürün; ( önce denendiği için bunlar zaten sıralıdır.

def generateParenthesis(n):
    result = []
    path = []

    def backtrack(opened, closed):
        if len(path) == 2 * n:
            result.append("".join(path))
            return
        # "(" sorts before ")", so trying it first keeps the output sorted
        if opened < n:
            path.append("(")
            backtrack(opened + 1, closed)
            path.pop()
        if closed < opened:  # only close a pair that is open
            path.append(")")
            backtrack(opened, closed + 1)
            path.pop()

    backtrack(0, 0)
    return result

Tuzaklar ve uç durumlar

Kurallar iki karşılaştırmadan ibaret olduğundan hatalar bu karşılaştırmalarda ve iki dalın sıralamasında gizlidir.

closed < opened yerine closed < n koşuluyla ) eklemek, ())( gibi dizeler oluşturur; bunlar hiç açılmamış bir çifti kapatır.
Bir dizenin yalnızca ( sayısı kadar ) içerdiğini kontrol etmek, )( dizgesini de kabul eder. Denge yalnızca sonda değil, her adımda 0 veya daha büyük olmalıdır.
( işaretinden önce ) işaretini denemek, doğru dizeleri ters sırada üretir ve sıralanmış yanıtla yapılan karşılaştırma başarısız olur.
Listelerin veya dize oluşturucuların değiştirilebilir olduğu bir dilde kopya yerine paylaşılan arabelleği kaydetmek: kaydedilen her yanıt aynı arabelleği gösterir ve geri izleme bu arabelleği yeniden boşaltır.
Sonuçlar için 2n yanıt kapasitesinde sabit bir dizi ya da küçük bir tahmine dayalı herhangi bir kapasite belirlemek: n = 8 için 1.430 yanıt vardır. Diziyi büyütün veya önce Catalan sayısını hesaplayın.

Sıkça sorulan sorular4

Generate Parentheses algoritmasının zaman karmaşıklığı nedir?

Geri izleme çözümü, C(n) = (2n)! / ((n+1)! n!) Catalan sayısı kadar dize üretir; bu sayı 4^n / (n^1.5 √π) gibi büyür. Her dizenin uzunluğu 2n olur ve arama hiçbir dalı boşa harcamaz; bu nedenle toplam süre O(4^n / √n) olur. Ek alan, geçerli dize ve çağrı yığını için O(n) kadardır; çıktının kullandığı alan buna dahil değildir.

n çift için kaç geçerli parantez dizgesi vardır?

Tam olarak n’inci Catalan sayısı: n 1’den 8’e kadar olduğunda 1, 2, 5, 14, 42, 132, 429 ve 1.430. Bunu görmenin bir yolu: Her düzgün biçimlenmiş dize ( + A + ) + B biçimindedir; burada ilk (, o ) ile eşleşir ve A ile B, aralarında toplam n-1 çift bulunan düzgün biçimlenmiş dizelerdir. A’nın boyutu üzerinden toplama yapmak Catalan bağıntısını verir.

closed < opened neden geçerli bir dizeyi garanti eder?

Bir dize, tam olarak eşleşmemiş bir ( olmadan bir ) geldiğinde bozulur; bu da ) sayısının ( sayısını aşacağı zamandır. ) karakterine yalnızca closed < opened iken izin vermek bunun olmasını engeller; ( karakterine yalnızca opened < n iken izin vermek ise her iki sayının da 2n uzunluğunda n'e ulaşmasını sağlar. Bu iki kural birlikte, düzgün biçimlendirilmiş bir dizenin her önekini tanımlar.

Generate Parentheses problemi özyineleme kullanılmadan çözülebilir mi?

Evet. Her biri iki sayacını içeren bir dize olan kısmi durumları bir yığında tut ve her durumu aynı iki kuralla genişlet. ) uzantısını ( uzantısından önce yığına eklersen, önce ( olan çıkar ve çıktı sıralı kalır. Yapılan iş aynıdır; kayıt tutma işi çağrı yığınından kendi yığınına taşınır.

Python

def generateParenthesis(n):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Girdi

n = 3

Beklenen

["((()))", "(()())", "(())()", "()(())", "()()()"]