Generate Parentheses

Q: Jaka jest złożoność czasowa Generate Parentheses?

Rozwiązanie z nawrotami generuje liczbę ciągów równą liczbie Catalana C(n) = (2n)! / ((n+1)! n!) , która rośnie jak 4^n / (n^1.5 √π) . Każdy ciąg ma długość 2n , a wyszukiwanie nigdy nie marnuje gałęzi, więc łączny czas wynosi O(4^n / √n) . Dodatkowe zużycie pamięci wynosi O(n) dla bieżącego ciągu i stosu wywołań, a także na wynik.

Q: Ile jest poprawnych ciągów nawiasów dla n par?

Dokładnie n-ta liczba Catalana: 1, 2, 5, 14, 42, 132, 429 i 1,430 dla n od 1 do 8. Można to zobaczyć tak: każdy poprawny ciąg ma postać ( + A + ) + B, gdzie pierwszemu ( odpowiada to ) , a A i B są poprawne i mają między sobą n-1 par. Sumując po rozmiarze A, otrzymujemy rekurencję Catalana.

Q: Dlaczego warunek closed < opened gwarantuje poprawny ciąg znaków?

Łańcuch znaków staje się niepoprawny dokładnie wtedy, gdy pojawia się ) , a przed nim nie ma niedopasowanego ( , czyli wtedy, gdy liczba ) przekraczałaby liczbę ( . Zezwalanie na ) tylko wtedy, gdy closed < opened , zapobiega temu, a zezwalanie na ( tylko wtedy, gdy opened < n , sprawia, że obie liczby osiągają n przy długości 2n . Razem te dwie reguły opisują każdy prefiks poprawnego łańcucha znaków.

Q: Czy problem Generowania nawiasów można rozwiązać bez rekurencji?

Tak. Przechowuj stos częściowych stanów, z których każdy jest ciągiem zawierającym dwa liczniki, i rozszerzaj stan, stosując te same dwie reguły. Jeśli umieścisz rozszerzenie ) na stosie przed rozszerzeniem ( , jako pierwsze zostanie zdjęte rozszerzenie ( , a wynik pozostanie uporządkowany. Praca jest taka sama; zarządzanie stanami przenosi się ze stosu wywołań na własny stos.

ŚrednieNawroty Rekurencja

+10

Ciąg nawiasów jest poprawny, gdy czytając go od lewej do prawej, liczba znaków ) nigdy nie przewyższa liczby znaków (, a na końcu obie liczby są równe. Zatem (())() jest poprawny, natomiast ())( nie jest: jego trzeci znak zamyka parę, która nigdy nie została otwarta.

Otrzymujesz liczbę całkowitą n. Zwróć wszystkie poprawne ciągi złożone z n nawiasów otwierających i n nawiasów zamykających, posortowane leksykograficznie, gdzie ( występuje przed ).

Funkcja

generateParenthesis(n: integer) → string-array

ninteger: liczba par nawiasów
Zwracastring-array: każdy poprawny ciąg n par, w porządku leksykograficznym

Ograniczenia

1 ≤ n ≤ 8
Dla n = 8 odpowiedź obejmuje 1 430 ciągów znaków.

Przykłady

Wejście: n = 3
Wyjście: ["((()))", "(()())", "(())()", "()(())", "()()()"]
Wyjaśnienie: Trzy pary można ułożyć na pięć poprawnych sposobów. ((())) otwiera wszystkie trzy, zanim zamknie którąkolwiek, a ponieważ ( sortuje się jako pierwsze, ten układ otwiera listę; ()()() od razu zamyka każdą parę i znajduje się na końcu.

Wejście: n = 1
Wyjście: ["()"]
Wyjaśnienie: Jedna para ma tylko jeden poprawnie utworzony układ. Jedyny inny ciąg składający się z jednego ( i jednego ) to )(, w którym nawias zamykający występuje, zanim pojawi się nawias otwierający.

+10 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy potrafisz policzyć poprawnie sformowane ciągi dla n par bez ich generowania?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Tylko niewielka część ciągów o długości 2n jest poprawnie sformowana: 5 z 64 ciągów dla n = 3 i 1,430 z 65,536 dla n = 8. Rozwiązaniem jest budowanie ciągu od lewej do prawej i dodawanie wyłącznie takich znaków, które zachowują jego poprawność, dzięki czemu wyszukiwanie nigdy nie wchodzi w gałąź, której nie da się dokończyć. O tym, co jest dozwolone, decydują dwa liczniki: ile znaków ( zostało już wstawionych i ile znaków ). Próbowanie ( przed ) na każdym kroku sprawia, że ciągi od razu są posortowane.

Utwórz każdy ciąg, a następnie go sprawdź

Intuicja

Bezpośrednia metoda polega na wypełnieniu 2n pozycji na wszystkie możliwe sposoby i zachowaniu ciągów, które są poprawnie zbudowane. Każda pozycja zawiera ( lub ), więc istnieje 2^(2n) = 4^n ciągów. Funkcja rekurencyjna umieszcza ( na następnej pozycji i wywołuje się rekurencyjnie, a następnie umieszcza tam ) i ponownie wywołuje się rekurencyjnie; każdy gotowy ciąg jest sprawdzany.

Sprawdzanie przechodzi przez ciąg, śledząc bilans: dodaje 1 dla ( i odejmuje 1 dla ). Ciąg jest poprawnie zbudowany, gdy bilans nigdy nie spada poniżej 0 i na końcu wynosi 0. Spadek poniżej 0 oznacza, że znak ) nie ma żadnego otwartego nawiasu do zamknięcia, jak na trzeciej pozycji w ciągu ())(.

Próbowanie ( przed ) na każdej pozycji wylicza ciągi w porządku leksykograficznym, ponieważ ( jest sortowany przed ). Zatem zachowane ciągi są już posortowane.

Koszt to 4^n ciągów, z których każdy jest sprawdzany w czasie O(n). Dla n = 8 oznacza to 65 536 ciągów i 1 430 odpowiedzi, więc około 98% pracy idzie na marne. Tutaj to działa, ponieważ n wynosi najwyżej 8, ale liczba ciągów zwiększa się czterokrotnie z każdą dodatkową parą, a metoda wciąż tworzy ciągi zaczynające się od ), mimo że już pierwszy znak je wyklucza.

Algorytm

Utrzymuj bufor o długości 2n znaków oraz listę odpowiedzi.
Napisz fill(pos). Jeśli pos jest równe 2n, sprawdź bufor i zapisz go, jeśli jest poprawnie sformowany.
W przeciwnym razie umieść ( na pozycji pos i wywołaj fill(pos + 1), a następnie umieść tam ) i wywołaj tę funkcję ponownie.
Aby sprawdzić ciąg, dodawaj 1 za każdy znak ( i odejmuj 1 za każdy znak ). Odrzuć go, gdy tylko bilans spadnie poniżej 0 lub jeśli na końcu nie wynosi 0.
Wywołaj fill(0) i zwróć zapisane ciągi, które są już posortowane.

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

Wycofywanie zmian w liczbie otwarć i zamknięć

Intuicja

Przenieś sprawdzanie do konstrukcji. Prefiks może jeszcze rozwinąć się w poprawny ciąg dokładnie wtedy, gdy spełnia dwa warunki: zawiera co najwyżej n nawiasów otwierających i nigdy liczba ) nie przekracza liczby (. Zatem na każdym kroku możesz dodać (, gdy opened < n, oraz ), gdy closed < opened. Gdy ciąg osiągnie długość 2n, obie liczby wynoszą n i ciąg jest poprawny — nie ma już nic do sprawdzenia.

Oto całe drzewo dla n = 2. Z pustego ciągu można dodać tylko (, ponieważ żaden nawias nie jest jeszcze otwarty. Po ( dozwolone są oba znaki. W gałęzi (( wartość opened wynosi już 2, więc pasuje tylko ); dodajemy je dwa razy, otrzymując (()). W gałęzi () żaden nawias nie jest otwarty, więc pasuje tylko (, a potem ), co daje ()(). Każda gałąź kończy się odpowiedzią: wyszukiwanie nigdy nie tworzy ciągu, który trzeba odrzucić.

Żadna odpowiedź nie zostaje pominięta. Każdy prefiks poprawnego ciągu spełnia oba warunki, więc wyszukiwanie nigdy nie odrzuca znaku, którego ten ciąg potrzebuje jako następnego, a każdy ciąg powstaje dokładnie raz, ponieważ jego znaki wyznaczają jedną ścieżkę w drzewie. Kolejność jest taka jak w pierwszym podejściu: dwa ciągi różnią się po raz pierwszy w miejscu, w którym rozdzielają się ich ścieżki, a gałąź ( jest tam przeszukiwana jako pierwsza.

Każdy liść jest odpowiedzią, a liczba odpowiedzi dla n par wynosi C(n), czyli liczbę Catalana, która rośnie jak 4^n / (n^1.5 √π). Każdy węzeł wewnętrzny leży na drodze do co najmniej jednego liścia, więc na każdą odpowiedź przypada najwyżej 2n węzłów wewnętrznych, a skopiowanie odpowiedzi kosztuje O(n). Łączny koszt to O(n × C(n)) = O(4^n / √n): dla n = 8 bezpośrednio powstaje 1,430 ciągów zamiast sprawdzania 65,536.

Algorytm

Zachowuj budowany ciąg znaków i dwa liczniki, opened oraz closed, oba równe 0.
Jeśli ciąg znaków ma długość 2n, zapisz jego kopię i zwróć.
Jeśli opened < n, dodaj (, wywołaj rekurencyjnie z opened + 1 i usuń go.
Jeśli closed < opened, dodaj ), wywołaj rekurencyjnie z closed + 1 i usuń go.
Rozpocznij od pustego ciągu znaków i zwróć zapisane ciągi, już posortowane, ponieważ najpierw sprawdzany jest (.

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

Pułapki i przypadki brzegowe

Reguły mieszczą się w dwóch porównaniach, więc błędy kryją się w tych porównaniach oraz w kolejności dwóch gałęzi.

Zezwolenie na ), gdy closed < n, zamiast gdy closed < opened, tworzy ciągi takie jak ())(, które zamykają parę, która nigdy nie została otwarta.
Sprawdzanie tylko, czy ciąg zawiera tyle samo ( co ), akceptuje )(. Bilans musi pozostawać równy 0 lub większy na każdym kroku, a nie tylko na końcu.
Próbowanie ) przed ( tworzy poprawne ciągi w odwrotnej kolejności, więc porównanie z posortowaną odpowiedzią kończy się niepowodzeniem.
Zapisywanie wspólnego bufora zamiast jego kopii w języku, w którym listy lub obiekty budujące ciągi są mutowalne: każda zapisana odpowiedź wskazuje wtedy na ten sam bufor, który cofanie zmian opróżnia.
Przeznaczenie stałej tablicy wyników na 2n odpowiedzi lub inną małą, zgadywaną liczbę: dla n = 8 jest 1,430 odpowiedzi. Zwiększaj rozmiar tablicy albo najpierw oblicz liczbę Catalana.

Najczęstsze pytania4

Jaka jest złożoność czasowa Generate Parentheses?

Rozwiązanie z nawrotami generuje liczbę ciągów równą liczbie Catalana C(n) = (2n)! / ((n+1)! n!), która rośnie jak 4^n / (n^1.5 √π). Każdy ciąg ma długość 2n, a wyszukiwanie nigdy nie marnuje gałęzi, więc łączny czas wynosi O(4^n / √n). Dodatkowe zużycie pamięci wynosi O(n) dla bieżącego ciągu i stosu wywołań, a także na wynik.

Ile jest poprawnych ciągów nawiasów dla n par?

Dokładnie n-ta liczba Catalana: 1, 2, 5, 14, 42, 132, 429 i 1,430 dla n od 1 do 8. Można to zobaczyć tak: każdy poprawny ciąg ma postać ( + A + ) + B, gdzie pierwszemu ( odpowiada to ), a A i B są poprawne i mają między sobą n-1 par. Sumując po rozmiarze A, otrzymujemy rekurencję Catalana.

Dlaczego warunek closed < opened gwarantuje poprawny ciąg znaków?

Łańcuch znaków staje się niepoprawny dokładnie wtedy, gdy pojawia się ), a przed nim nie ma niedopasowanego (, czyli wtedy, gdy liczba ) przekraczałaby liczbę (. Zezwalanie na ) tylko wtedy, gdy closed < opened, zapobiega temu, a zezwalanie na ( tylko wtedy, gdy opened < n, sprawia, że obie liczby osiągają n przy długości 2n. Razem te dwie reguły opisują każdy prefiks poprawnego łańcucha znaków.

Czy problem Generowania nawiasów można rozwiązać bez rekurencji?

Tak. Przechowuj stos częściowych stanów, z których każdy jest ciągiem zawierającym dwa liczniki, i rozszerzaj stan, stosując te same dwie reguły. Jeśli umieścisz rozszerzenie ) na stosie przed rozszerzeniem (, jako pierwsze zostanie zdjęte rozszerzenie (, a wynik pozostanie uporządkowany. Praca jest taka sama; zarządzanie stanami przenosi się ze stosu wywołań na własny stos.

Python

def generateParenthesis(n):
    # Napisz tutaj kod

Przypadki testowe

Przypadek 1

Przypadek 2

Wejście

n = 3

Oczekiwane

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