---
title: Valid Parentheses
difficulty: Easy
category: Stack
leetcode_id: 20
revision_count: 1
last_revision: 2026-09-12
---

# Valid Parentheses

> **LeetCode:** [#20](https://leetcode.com/problems/valid-parentheses/)
> **Сложность:** Easy
> **Категория:** Stack

## Условие

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

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

## Ключевая идея

Используем стек: при открывающей скобке кладём её в стек; при закрывающей — проверяем, что стек не пуст и верхушка стека — парная открывающая скобка. В конце стек должен быть пуст.

## Оценка сложности

- **Время:** O(n) — один проход по строке
- **Память:** O(n) — стек хранит до n/2 элементов в худшем случае (все открывающие)

## Решение (Ruby)

```ruby
# @param {String} s
# @return {Boolean}
def is_valid(s)
  pairs = { ')' => '(', '}' => '{', ']' => '[' }
  stack = []

  s.each_char do |c|
    if pairs.key?(c)
      return false if stack.empty? || stack.pop != pairs[c]
    else
      stack.push(c)
    end
  end

  stack.empty?
end
```

## Разбор на примере

```
s = "([])"

stack = []
c='('  открывающая → stack.push('(')  ⇒ stack=['(']
c='['  открывающая → stack.push('[')  ⇒ stack=['(', '[']
c=']'  закрывающая → stack.pop ⇒ stack=['('], pop='[' == pairs[']']='[' → ok
c=')'  закрывающая → stack.pop ⇒ stack=[],  pop='(' == pairs[')']='(' → ok
stack.empty? → true
```

```
s = "(]"

stack = []
c='('  открывающая → stack.push('(')  ⇒ stack=['(']
c=']'  закрывающая → stack.pop ⇒ stack=[], pop='(' != pairs[']']='[' → false
```

## Edge Cases

- **Пустая строка**: `s = ""` → `stack.empty?` → `true`.
- **Один символ**: `s = "("` → стек не пуст → `false`.
- **Закрывающая без открывающей**: `s = ")"` → `stack.empty?` на первом символе → `false`.
- **Неправильный порядок**: `s = "({)}"` → `stack = ['(', '{']`, встречаем `)`, pop = `{` ≠ `(` → `false`.
- **Длинная вложенная последовательность**: `s = "(((...)))"` — стек растёт и схлопывается, O(n) памяти.

## Типичные ошибки

- **Не проверять `stack.empty?` перед `pop`**: если строка начинается с `)`, `stack.pop` вернёт `nil` и может случайно пройти проверку (nil == nil для пустого хэша).
- **Путать направление маппинга**: маппинг `{ '(' => ')' }` заставляет проверять наоборот — проще маппить закрывающие → открывающие.
- **Забыть `stack.empty?` в конце**: строка с одной открывающей скобкой пройдёт проверки, но будет невалидной.
- **Использовать счётчик для одного типа скобок**: для трёх типов счётчик не работает, нужен стек.

## Альтернативные подходы

| Подход | Время | Память | Комментарий |
|--------|-------|--------|-------------|
| Замена подстрок (replace) | O(n²) | O(n) | Пока есть `()`, `[]`, `{}` — заменяем на пустую строку. Медленно, но интуитивно. |
| **Стек (оптимальный)** | **O(n)** | **O(n)** | **Один проход, простая проверка. Финальное решение.** |

## Заметки после повторения

_Что забыл? Что пошло не так? На чём застрял? Заполни после каждой тренировки._