---
round: 1
ticket_no: 30
source_no: 13
slug: valid-parentheses
topic: Queue / Stack
difficulty: Easy
leetcode_id: 20
attempted: true
score: 2
verdict: partial
reviewed_at: 2026-09-12
---

# Билет 30 — Valid Parentheses

## Условие (как предъявлено)

Дана строка `s`, состоящая только из символов `(`, `)`, `{`, `}`, `[` и `]`. Нужно определить, является ли строка корректной: каждая открывающая скобка закрывается скобкой того же типа в правильном порядке.

```
Input:  s = "()"      →  true
Input:  s = "()[]{}"  →  true
Input:  s = "(]"      →  false
Input:  s = "([])"    →  true
Input:  s = "([)]"    →  false
```

Constraints: `1 <= length <= 10^4`.

## Ответ

> Так как у нас здесь скобки разного номинала, поэтому одним счётчиком мы здесь не отделаемся — для нас важен порядок, здесь подходит стек. То есть, когда нам встречается открывающаяся скобка, мы добавляем её в стек. Когда скобка закрывается, мы проверяем, что у нас на вершине стека соответствующая скобка. Если да, тогда мы сгорают обе, да, то есть мы оттуда убираем. Если разномастные, значит у нас ошибка. Всё, возвращаем ошибку. То есть в конце у нас стек должен оказаться пустым. Вот такая история. Тут, наверное, может быть большой стек получится. Что здесь можно сделать сходу, не могу понять, то что порядок важен. Стек тут кажется эффективен.

## Разбор

**Что верно:** стек: открывающие кладём, на закрывающей проверяем вершину и снимаем, в конце стек должен быть пуст — эталонное решение.

**Что упущено и ошибки:** не проговорена проверка «стек не пуст» перед сравнением вершины (иначе строка, начинающаяся с закрывающей скобки, ломает решение); не названа сложность O(n) / O(n); граничные случаи (n = 1, строка только из закрывающих).

**Эталонная идея:** pairs = { ")" => "(", "]" => "[", "}" => "{" }; stack = []; при открывающей push, при закрывающей проверить stack.last и pop; вернуть stack.empty?.

**Сложность:** время O(n), память O(n)

**Критерии:** идея ✅ · структура данных ✅ · сложность ❌ · граничные случаи ⚠️


**Разбор задачи:** [`../../algo-solutions/01-must-have/04-queue-stack/13-valid-parentheses.md`](../../algo-solutions/01-must-have/04-queue-stack/13-valid-parentheses.md)