Valid Parentheses

Лёгкая№20скобки

Дана строка из скобок ( ) [ ] { }. Она правильная, если каждую скобку закрывает скобка того же вида и пары не перекрещиваются: что открыли последним, то и закрывают первым. Наш пример, два вызова: "{[()()]}" — true, "(()[]" — false, первую "(" так и не закрыли.

20 Valid ParenthesesРазбор · 1×

Пример: "{[()()]}" и "(()[]". Под строками — стек закрывающих, которые ещё ждём, самая новая справа.

вызов 1{[()()]}вызов 2(()[]expect—
ещё не прочитанаch, читаем сейчас; только что положенная закрывающаяоткрыта, её закрывающую ждёмсняли для сравнения; так и не закрытазакрыта в паре

Первый вызов, s = "{[()()]}": пока ничего не ждём

01/43
сначала · назад · пуск · шаг
Скорость
1function isValid(s):
2 expect = empty stack
3 for each ch in s:
4 if ch is ( or [ or {:
5 push closerOf(ch) onto expect
6 else if expect is empty:
7 return false
8 else if pop from expect is not ch:
9 return false
10 return expect is empty
состояние
s
"{[()()]}"
expect
[]
ch
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Пары не перекрещиваются, поэтому закрывающая должна подойти к самой новой ещё открытой скобке — к верху стека. Если класть закрывающую, которую она ждёт, проверка сводится к одному сравнению.
  2. Совпавшую пару сразу снимаем, поэтому всё вложенное уходит раньше, чем придёт внешняя закрывающая, и внешняя открывающая снова оказывается сверху.
  3. Две ошибки ловятся отдельно: закрывающая, когда ничего не ждём, и открывающая, которая всё ещё ждёт, когда строка кончилась. Поэтому последняя строка спрашивает, пуст ли стек.

Сложность

Время O(n): каждую скобку кладём или снимаем один раз. Память O(n): если в строке одни открывающие, в стеке окажутся все.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.