Дана строка из символов ()[]{}. Проверьте, является ли она корректной скобочной последовательностью: каждая скобка закрыта парной в правильном порядке.
Короткий ответ
- Последняя открытая скобка закрывается первой — это стек
- Открывающую кладём в стек
- Закрывающая должна совпасть с вершиной стека
- Несовпадение или пустой стек при закрывающей — ответ нет
- В конце стек должен быть пуст
- Словарь пар закрывающая → открывающая упрощает проверку
Стек с проверкой вершины на каждой закрывающей скобке решает задачу за O(n) по времени и O(n) по памяти в худшем случае.
Как сказать вслух
пример ответаКлючевое наблюдение: скобки закрываются в порядке, обратном открытию, а это поведение стека. Открывающие кладу в стек, на закрывающей снимаю вершину и сверяю тип. Если вершина не совпала, стек пуст на закрывающей или не пуст в конце — последовательность некорректна.
Подробный ответ
Основной ответ
Корректная последовательность обладает свойством LIFO: закрывающая скобка всегда парна последней незакрытой открывающей, поэтому естественная структура — стек. Проходим строку: открывающую скобку push-им; для закрывающей проверяем, что стек непуст и на вершине лежит парная открывающая, и снимаем её — иначе сразу возвращаем False. После прохода последовательность корректна, только если стек пуст: оставшиеся элементы — незакрытые скобки. Удобно завести словарь соответствий закрывающих к открывающим, чтобы не писать три ветки условий. Время O(n) — один проход с O(1) операциями, память O(n) в худшем случае (строка из одних открывающих). Полезный ранний выход: строка нечётной длины корректной быть не может.
Ключевые моменты
- Почему стек. Вложенность скобок — это LIFO: последняя открытая закрывается первой, и стек моделирует это напрямую.
- Три условия отказа. Закрывающая при пустом стеке, несовпадение типа на вершине, непустой стек после прохода — все три надо проверить.
- Словарь пар. Отображение ')' → '(' и т.д. сводит проверку к одному сравнению вместо перечисления случаев.
- Сложность. O(n) времени, O(n) памяти в худшем случае; лучше не бывает — каждый символ нужно прочитать.
Практический контекст
Задача проверяет владение стеком и аккуратность с граничными случаями. Интервьюер почти наверняка спросит про пустую строку (корректна), строку из одних закрывающих и строку из одних открывающих. Расширения, к которым стоит быть готовым: минимальное число удалений до корректной строки, скобки со звёздочкой-джокером, самая длинная корректная подстрока.
Пример кода
def is_valid(s):
pairs = {')': '(', ']': '[', '}': '{'}
stack = []
for ch in s:
if ch in pairs: # закрывающая
if not stack or stack.pop() != pairs[ch]:
return False
else: # открывающая
stack.append(ch)
return not stack
assert is_valid('()[]{}')
assert is_valid('{[()]}')
assert not is_valid('([)]')
assert not is_valid('((')
assert not is_valid(')')Частые ошибки
- Забывают финальную проверку пустоты стека — строка '((' проходит как корректная
- Не проверяют пустой стек перед pop и ловят исключение на строке ')'
- Считают скобки счётчиками по типам, что пропускает неверный порядок вроде '([)]'