---
round: 3
ticket_no: 16
source_no: 13
slug: valid-parentheses
topic: Queue / Stack
difficulty: Easy
leetcode_id: 20
attempted: true
score:
verdict:
reviewed_at:
---

# Билет 16 — Valid Parentheses

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

Дана строка `s`, содержащая только символы `'('`, `')'`, `'['`, `']'`, `'{'` и `'}'`. Определите, является ли входная строка валидной.

Строка валидна, если:
- открывающие скобки закрыты скобками того же типа;
- открывающие скобки закрыты в правильном порядке;
- каждая закрывающая скобка имеет соответствующую открывающую.

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

Constraints: `1 <= s.length <= 10^4`; строка состоит только из скобок `()[]{}`.

## Ответ

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

## Разбор

**Что верно:**

**Что упущено и ошибки:**

**Эталонная идея:**

**Время:** O(...) — что доминирует

**Память:** O(...) дополнительная (+ O(...) на выход / стек рекурсии)

**Граничные случаи:** 1) ... 2) ... 3) ...

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

**Канон сложности:** сверить с [`../complexity-cheat-sheet.md`](../complexity-cheat-sheet.md) (таблица по 32 задачам)

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