Почему это работает
- Пары не перекрещиваются, поэтому закрывающая должна подойти к самой новой ещё открытой скобке — к верху стека. Если класть закрывающую, которую она ждёт, проверка сводится к одному сравнению.
- Совпавшую пару сразу снимаем, поэтому всё вложенное уходит раньше, чем придёт внешняя закрывающая, и внешняя открывающая снова оказывается сверху.
- Две ошибки ловятся отдельно: закрывающая, когда ничего не ждём, и открывающая, которая всё ещё ждёт, когда строка кончилась. Поэтому последняя строка спрашивает, пуст ли стек.
Сложность
Время O(n): каждую скобку кладём или снимаем один раз. Память O(n): если в строке одни открывающие, в стеке окажутся все.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗