Валидация скобочной последовательности (3 вида скобок)

Нельзя обойти стороной одну из самых мейнстримных задач на собеседованиях — валидация скобочной последовательности. Тот читатель, кто время от времени ходит по собесдованиям и имеет десяток-два продйенных алгоритмических секции, почти со стопроцентной вероятностью сталкивался с ней. Она настолько популярна, что давно перешла из разряда средне-сложных в разряд легких и, скорее всего, в известных компаниях, практикующих эту секцию, если и попадется вам, то в самом начале собеседования, как «разминочная».

Но, все же, разобрать ее просто необходимо. Эта задача имеет каноническое оптимальное решение через стек, которое от вас будет ждать любой интервьер (хотя, безусловно, это не единственно возможный подход).

Сложность: 🟢 Легкая

ℹ️ Описание

Дана строка, состоящий только из скобок «(», «)», «{», «}», «[» и «]». Напишите функцию, определяющую, является ли строка правильной скобочной последовательностью.

⚠️ Ограничения

🔹Длина строки от 1 до 10000 символов
🔹Строка состоит только из символов «(», «)», «{», «}», «[» и «]».


1️⃣ Пример

Входящие данные: "()"
Ответ: true
Объяснение: все открывающие скобки имеют соотвествующую закрывающую скобку, открывающие и закрывающие скобки расположены в правильном порядке, в строке нет закрывающих скобок без предварительно открывающей пары.

2️⃣ Пример

Входящие данные: "()[]{}"
Ответ: true
Объяснение: все открывающие скобки имеют соотвествующую закрывающую скобку, открывающие и закрывающие скобки расположены в правильном порядке, в строке нет закрывающих скобок без предварительно открывающей пары.

3️⃣ Пример

Входящие данные: "(]"
Ответ: false
Объяснение: открывающая и закрывающая скобки относятся к разным типам скобок


✅ Решение

Для решения задачи мы воспользуемся структурой данных стек (можно реализовать через обычный массив). Будем идти по строчке посимвольно.

🔘 Если символ — одна из открывающих скобок, кладем ее в стек.

🔘 Если символ — одна из закрывающих скобок, пытаемся извлечь верхний элемент из стека:
⏺ если в стеке нет эементов, значит последовательность невалидна и мы столкнулись с закрывающей скобкой для которой нет открывающей;
⏺ если верхний элемент — это открывающая скобка другого типа, значит последовательность невалидна и мы столкнулись с кейсом неверной пары (например "(]");
⏺ если верхний элемент — это открывающая скобка нужного типа, то просто идем дальше.

🔘 Если после итерации по всем симолам строки в стеке остались какие-либо элементы, значит последовательность невалидна (есть открывающие скобки, для которых нет открывающей пары). В противном случае — последовательность валидна.

Посмотреть реализацию

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

По времени
Чтобы провалидировать строку, нам достаточно один раз проитерироваться по всем символам, то есть сложность равна O(n),
где n — длина строки.

По памяти
Нам понадобится промежуточный стек, в который в худшем случае мы поместим все символы строки (например, для строки "((((("). То есть сложность по памяти также равна O(n), где n — длина строки.

#strings #stack #easy