Generate Parentheses

Q: Generate Parentheses'in zaman karmaşıklığı nedir?

Geri izleme, Catalan sayısı olan C(n) = (2n)! / ((n+1)! n!) dizesini üretir; bu sayı 4^n / (n^1.5 √π) oranında büyür. Her birini oluşturup kopyalamak O(n) sürer, dolayısıyla zaman karmaşıklığı 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 eklenir.

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

1'den 8'e kadar n için n'inci Catalan sayısı: 1, 2, 5, 14, 42, 132, 429 ve 1.430. Her iyi biçimlendirilmiş dize ( A ) B biçiminde ayrılır; burada bu ) , ilk ( ile eşleşir ve A ile B toplam n - 1 çift paylaşır. A'nın boyutu üzerinden toplama yapmak Catalan bağıntısını verir.

Q: Generate Parentheses problemi özyineleme olmadan çözülebilir mi?

Evet. Her biri iki sayacını içeren bir dizge olan kısmi durumları bir yığında tut ve her durumu aynı iki kurala göre genişlet. ) uzantısını ( uzantısından önce yığına ekle; böylece önce ( uzantısı çıkarılır ve çıktı sıralı kalır.

OrtaGeri izleme Özyineleme

+10

Bir parantez dizisi, soldan sağa okunurken ) sayısı hiçbir zaman ( sayısını geçmiyorsa ve sonunda iki sayı eşitse düzgün biçimlidir. Bu nedenle (())() düzgün biçimlidir, ancak ())( değildir: üçüncü karakteri, hiç açılmamış bir çifti kapatır.

Bir n tam sayısı verildiğinde, n açılış ve n kapanış parantezi içeren tüm düzgün biçimli dizileri, ( karakterinin ) karakterinden önce geldiği sözlük sırasına göre sıralanmış olarak döndür.

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çimlenmiş dizgeyi sözlük sırasına göre

Kısıtlar

1 ≤ n ≤ 8
n = 8 için yanıt 1.430 dizgedir.

Örnekler

Girdi: n = 3
Çıktı: ["((()))", "(()())", "(())()", "()(())", "()()()"]
Açıklama: Üç çift, iyi biçimlendirilmiş beş dize oluşturur. ((())) önce üçünü de açar, bu yüzden ilk sırada yer alır; ()()() her çifti hemen kapatır ve son sırada yer alır.

Girdi: n = 1
Çıktı: ["()"]
Açıklama: Bir eşleşmede düzgün biçimlendirilmiş bir dize bulunur. Diğer tek düzenleme olan )(, herhangi bir şey açılmadan önce kapatılır.

Ek soru

n çift için geçerli dizeleri oluşturmadan sayabilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

2n uzunluğundaki dizgelerin çok azı düzgün biçimlidir: n = 8 için 65.536 dizgeden 1.430'u. Her dizgeyi soldan sağa oluşturun ve yalnızca önek hâlâ tamamlanabiliyorsa bir karakter ekleyin. Buna iki sayaç karar verir; ( karakterini ) karakterinden önce denemek, dizgelerin sıralı çıkmasını sağlar.

Her dizeyi oluştur, ardından kontrol et

Sezgi

2n konumu, ( ve ) karakterlerinin tüm kombinasyonlarıyla doldur; 4^n dizeyi oluştur ve düzgün biçimlendirilmiş olanları tut. Bir diziyi kontrol etmek için, bir denge değeri kullanarak üzerinde ilerle: ( için 1 ekle, ) için 1 çıkar. Denge değeri hiçbir zaman 0'ın altına düşmüyorsa ve 0'da bitiyorsa dize düzgün biçimlendirilmiştir. Her konumda ( karakterini ) karakterinden önce yerleştirmek, dizeleri sıralı olarak listeler.

Her dizenin kontrolü O(n) maliyetindedir. n = 8 için 1.430 yanıt karşılığında 65.536 dize vardır; dolayısıyla işin yaklaşık %98'i boşa gider ve her ek parantez çiftiyle bu miktar dört katına çıkar.

Algoritma

2n karakterlik bir arabellek ve yanıtlar için bir liste tut.
fill(pos): pos 2n'ye eşitse, düzgün biçimlendirilmişse arabelleği kaydet.
Aksi hâlde pos konumuna ( koy ve fill(pos + 1) çağrısını yap; ardından oraya ) koy ve aynı işlevi tekrar çağır.
Kontrol etmek için, her ( için 1 ekle ve her ) için 1 çıkar. Denge 0'ın altına düşerse veya 0'da bitmezse reddet.
fill(0) çağrısını yap ve kaydedilen dizeleri döndür.

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çma ve kapatma sayıları üzerinde geri izleme

Sezgi

Denetimi oluşturma işleminin içine taşı. Bir önek, yalnızca en fazla n tane ( içeriyorsa ve hiçbir zaman ) sayısı ( sayısını aşmıyorsa düzgün biçimlenmiş bir dizeye dönüşebilir. Bu nedenle opened < n iken (, closed < opened iken ) eklenebilir. Uzunluk 2n olduğunda her iki sayı da n olur ve dizenin düzgün biçimlenmiş olduğu artık kontrol edilmesi gereken bir şey kalmadığı için bellidir.

Hiçbir yanıt atlanmaz; çünkü düzgün biçimlenmiş bir dizenin her öneki her iki kurala da uyar. Hiçbir dal boşa harcanmaz: n = 2 için (( dalı yalnızca iki kez kapatılabilir ve böylece (()) elde edilir; () dalı ise yalnızca açılıp kapanabilir ve böylece ()() elde edilir. Her dize ağaçta tek bir yolu izlediğinden yalnızca bir kez görünür ve ( dalı önce geldiğinden çıktı sıralıdır.

Her yaprak bir yanıttır; bu nedenle yapılan iş çıktı miktarıyla orantılıdır: O(4^n / √n).

Algoritma

Oluşturulan dizeyi ve opened ile closed adlı iki sayacı, ikisi de 0 olacak şekilde tut.
Dizenin uzunluğu 2n ise bir kopyasını kaydet ve dön.
opened < n ise ( ekle, opened + 1 ile özyinelemeli çağrı yap ve onu çıkar.
closed < opened ise ) ekle, closed + 1 ile özyinelemeli çağrı yap ve onu çıkar.
Boş dizeyle başla ve kaydedilen dizeleri döndü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

closed < opened yerine closed < n koşulunda ) eklemeye izin vermek. Bu, hiç açılmamış bir çifti kapatan ())( dizgesini oluşturur.
Yalnızca sonunda sayıların eşit olup olmadığını kontrol etmek. Bu, )( dizgesini kabul eder; denge her adımda 0 veya daha büyük kalmalıdır.
( yerine ) karakterini önce denemek. Doğru dizgeler ters sırada ortaya çıkar.
Listelerin veya dizge oluşturucuların değiştirilebilir olduğu durumlarda, ortak tamponun bir kopyası yerine kendisini kaydetmek. Böylece kaydedilen her yanıt aynı tamponu gösterir ve geri izleme bu tamponu yeniden boşaltır.
Sabit sonuç dizisinin boyutunu küçük bir tahmine göre belirlemek. n = 8 için 1.430 yanıt vardır.

Sıkça sorulan sorular3

Generate Parentheses'in zaman karmaşıklığı nedir?

Geri izleme, Catalan sayısı olan C(n) = (2n)! / ((n+1)! n!) dizesini üretir; bu sayı 4^n / (n^1.5 √π) oranında büyür. Her birini oluşturup kopyalamak O(n) sürer, dolayısıyla zaman karmaşıklığı 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 eklenir.

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

1'den 8'e kadar n için n'inci Catalan sayısı: 1, 2, 5, 14, 42, 132, 429 ve 1.430. Her iyi biçimlendirilmiş dize ( A ) B biçiminde ayrılır; burada bu ), ilk ( ile eşleşir ve A ile B toplam n - 1 çift paylaşır. A'nın boyutu üzerinden toplama yapmak Catalan bağıntısını verir.

Generate Parentheses problemi özyineleme olmadan çözülebilir mi?

Evet. Her biri iki sayacını içeren bir dizge olan kısmi durumları bir yığında tut ve her durumu aynı iki kurala göre genişlet. ) uzantısını ( uzantısından önce yığına ekle; böylece önce ( uzantısı çıkarılır ve çıktı sıralı kalır.

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

Test #1

Test #2

Argüman

n = 3

Beklenen Çıktı

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