Валидация скобочной последовательности (3 вида скобок)
Нельзя обойти стороной
одну из самых мейнстримных задач на собеседованиях —
валидация скобочной последовательности. Тот читатель, кто время от времени ходит по собесдованиям и имеет десяток-два продйенных алгоритмических секции, почти со стопроцентной вероятностью сталкивался с ней. Она настолько популярна, что давно перешла из разряда средне-сложных в разряд легких и, скорее всего, в известных компаниях, практикующих эту секцию, если и попадется вам, то в самом начале собеседования, как «разминочная».
Но, все же, разобрать ее просто необходимо. Эта задача имеет каноническое оптимальное решение через
стек, которое от вас будет ждать любой интервьер (хотя, безусловно, это не единственно возможный подход).
Сложность: 🟢 Легкая
ℹ️
ОписаниеДана строка, состоящий только из скобок «(», «)», «{», «}», «[» и «]». Напишите функцию, определяющую, является ли строка
правильной скобочной последовательностью.
⚠️
Ограничения🔹Длина строки от 1 до 10000 символов
🔹Строка состоит только из символов «(», «)», «{», «}», «[» и «]».
1️⃣
ПримерВходящие данные: "()"
Ответ: true
Объяснение: все открывающие скобки имеют соотвествующую закрывающую скобку, открывающие и закрывающие скобки расположены в правильном порядке, в строке нет закрывающих скобок без предварительно открывающей пары.
2️⃣
ПримерВходящие данные: "()[]{}"
Ответ: true
Объяснение: все открывающие скобки имеют соотвествующую закрывающую скобку, открывающие и закрывающие скобки расположены в правильном порядке, в строке нет закрывающих скобок без предварительно открывающей пары.
3️⃣
ПримерВходящие данные: "(]"
Ответ: false
Объяснение: открывающая и закрывающая скобки относятся к разным типам скобок
✅
РешениеДля решения задачи мы воспользуемся структурой данных
стек (можно реализовать через обычный массив). Будем идти по строчке посимвольно.
🔘 Если символ — одна из открывающих скобок, кладем ее в стек.
🔘 Если символ — одна из закрывающих скобок, пытаемся извлечь верхний элемент из стека:
⏺ если в стеке нет эементов, значит последовательность невалидна и мы столкнулись с закрывающей скобкой для которой нет открывающей;
⏺ если верхний элемент — это открывающая скобка другого типа, значит последовательность невалидна и мы столкнулись с кейсом неверной пары (например "(]");
⏺ если верхний элемент — это открывающая скобка нужного типа, то просто идем дальше.
🔘 Если после итерации по всем симолам строки в стеке остались какие-либо элементы, значит последовательность невалидна (есть открывающие скобки, для которых нет открывающей пары). В противном случае — последовательность валидна.
Решение на GOРешение на TypeScript🅾️
Оценка сложностиПо времениЧтобы провалидировать строку, нам достаточно один раз проитерироваться по всем символам, то есть сложность равна
O(n),
где n — длина строки.
По памятиНам понадобится промежуточный стек, в который в худшем случае мы поместим все символы строки (например, для строки "((((("). То есть сложность по памяти также равна
O(n), где n — длина строки.
#strings #stack #easy