Valid Parentheses

Q: Jaka jest złożoność czasowa problemu poprawnych nawiasów?

Rozwiązanie z użyciem stosu działa w czasie O(n) , ponieważ każdy znak jest dodawany na stos lub zdejmowany ze stosu co najwyżej raz. W najgorszym przypadku, gdy ciąg składa się wyłącznie ze znaków otwierających, zajmuje O(n) miejsca. Wielokrotne usuwanie dopasowanych par zajmuje O(n²) czasu, ponieważ w każdym kroku z głęboko zagnieżdżonego ciągu usuwana jest tylko jedna para.

ŁatweStos

+10

Otrzymujesz ciąg znaków s złożony wyłącznie ze znaków nawiasów (, ), [, ], { i }. Zwróć true, gdy nawiasy są zrównoważone: każdy nawias zamykający zamyka ostatni nadal otwarty nawias, oba są tego samego rodzaju i na końcu żaden nawias nie pozostaje otwarty. W przeciwnym razie zwróć false.

Funkcja

isValid(s: string) → boolean

sstring: ciąg nawiasów do sprawdzenia
Zwracaboolean: czy nawiasy są zrównoważone

Ograniczenia

1 ≤ s.length ≤ 10⁴
s zawiera tylko znaki (, ), [, ], { i }.

Przykłady

Wejście: s = "[]{}()"
Wyjście: true
Wyjaśnienie: Trzy pary stoją obok siebie i każda zamyka się zaraz po otwarciu.

Wejście: s = "{(})"
Wyjście: false
Wyjaśnienie: Znak } pojawia się, gdy nawias ( otwarty po nim jest nadal otwarty, więc zamyka niewłaściwy rodzaj nawiasu.

Pytanie dodatkowe

Jeśli ciąg zawierałby tylko nawiasy okrągłe, czy dałoby się sprawdzić go za pomocą jednego licznika zamiast stosu, używając dodatkowo O(1) miejsca?

Rozwiązanie

Samo liczenie nawiasów nie wystarczy: {(}) zawiera po jednym nawiasie otwierającym i zamykającym, a mimo to jest niepoprawny, ponieważ kolejność ma znaczenie. Stos przechowuje nadal otwarte nawiasy w kolejności ich otwierania, więc jedno przejście z użyciem stosu wystarczy, by ocenić cały ciąg.

Wielokrotnie usuwaj dopasowane pary

Poprawne, ale nie kończy się na największych testach

Intuicja

Każdy poprawny nawiasowo ciąg znaków ma najbardziej wewnętrzną parę, między której nawiasami nic się nie znajduje, taką jak () wewnątrz {[()]}. Usunięcie sąsiadującej, dopasowanej pary nigdy nie zmienia tego, czy ciąg jest poprawny nawiasowo. Powtarzaj więc usuwanie, aż w którejś rundzie nic nie zostanie usunięte: poprawny nawiasowo ciąg skraca się do pustego, a niepoprawny utknie z pozostałymi znakami, tak jak {(}) już od początku.

Każda runda przegląda cały ciąg i tworzy jego nową kopię, a zagnieżdżony ciąg, taki jak (((...))), traci jedną parę w każdej rundzie. To maksymalnie n/2 rund po O(n) pracy, czyli łącznie O(n²).

Algorytm

Usuń każde (), [] i {} z ciągu znaków.
Jeśli w tej rundzie niczego nie usunięto, zatrzymaj się.
W przeciwnym razie powtórz czynność dla krótszego ciągu znaków.
Zwróć true, jeśli ciąg znaków jest pusty, a false, jeśli pozostał jakikolwiek nawias.

def isValid(s):
    while True:
        # Delete every adjacent matched pair in one round.
        shorter = s.replace("()", "").replace("[]", "").replace("{}", "")
        if shorter == s:
            break  # nothing left to delete
        s = shorter
    return s == ""

Jedno przejście ze stosem

Intuicja

Nawias zamykający musi zamknąć nawias otwarty najpóźniej spośród tych, które nadal są otwarte. Ostatni otwarty nawias zamyka się jako pierwszy, a tę kolejność „ostatni wszedł, pierwszy wyszedł” zachowuje właśnie stos.

Umieszczaj na stosie nawias zamykający, na który czeka każdy nawias otwierający. Nawias zamykający musi być wtedy równy elementowi ze szczytu stosu. Pusty stos oznacza, że nie ma czego zamknąć; inny element na szczycie oznacza, że zamykany jest niewłaściwy rodzaj nawiasu — tak jak } w {(}), gdy na szczycie znajduje się ). Na końcu wszystko, co pozostało na stosie, jak w ((, zostało otwarte i nigdy niezamknięte. Każdy znak jest raz umieszczany na stosie albo z niego zdejmowany: czas O(n) i najwyżej n elementów na stosie.

Algorytm

Utwórz pusty stos.
Dla nawiasu otwierającego umieść na stosie odpowiadający mu nawias zamykający.
Dla nawiasu zamykającego zwróć false, jeśli stos jest pusty lub jego wierzchołek zawiera inny znak; w przeciwnym razie zdejmij element ze stosu.
Po ostatnim znaku zwróć true tylko wtedy, gdy stos jest pusty.

def isValid(s):
    closers = {'(': ')', '[': ']', '{': '}'}
    stack = []
    for ch in s:
        if ch in closers:
            stack.append(closers[ch])
        elif not stack or stack.pop() != ch:
            return False
    return not stack

Pułapki i przypadki brzegowe

Liczenie każdego rodzaju nawiasów. {(}) ma zgodną liczbę nawiasów, a mimo to jest nieprawidłowe, natomiast )( nie spełnia warunku wyłącznie ze względu na kolejność.
Usuwanie elementu z pustego stosu. Ciąg, który zaczyna się od nawiasu zamykającego, takiego jak } lub )]}, musi zwracać false, zamiast powodować awarię.
Pominięcie końcowego sprawdzenia. (([{ nigdy nie napotyka niewłaściwego nawiasu zamykającego, więc tylko pozostałe elementy stosu wskazują, że ciąg jest nieprawidłowy.
Poleganie na długości. Ciąg o nieparzystej długości jest zawsze nieprawidłowy, ale parzysta długość niczego nie dowodzi: zarówno (], jak i ())( są nieprawidłowe.
W podejściu polegającym na usuwaniu — przekazywanie nawiasów do wyrażenia regularnego lub wzorca Lua bez poprzedzania ich znakami ucieczki. ( i [ mają tam specjalne znaczenie; użyj zamiany zwykłego tekstu.

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu poprawnych nawiasów?

Rozwiązanie z użyciem stosu działa w czasie O(n), ponieważ każdy znak jest dodawany na stos lub zdejmowany ze stosu co najwyżej raz. W najgorszym przypadku, gdy ciąg składa się wyłącznie ze znaków otwierających, zajmuje O(n) miejsca. Wielokrotne usuwanie dopasowanych par zajmuje O(n²) czasu, ponieważ w każdym kroku z głęboko zagnieżdżonego ciągu usuwana jest tylko jedna para.

Dlaczego do sprawdzania poprawności nawiasów używa się stosu?

Nawiasy zagnieżdżają się, więc nawias otwarty jako ostatni musi zostać zamknięty jako pierwszy. Stos przechowuje ten nawias na wierzchu, skąd można go odczytać i usunąć w stałym czasie, dzięki czemu całe sprawdzanie zajmuje O(n).

Czy pusty ciąg znaków jest poprawnym nawiasowaniem?

Tak. Pusty ciąg nie zawiera niedopasowanego nawiasu, więc jest zrównoważony: stos pozostaje pusty, a pętla usuwająca nie ma nic do usunięcia. W tym problemie s zawsze zawiera co najmniej jeden znak.