Еще одна очень часто встречающаяся задача на собеседовании. Относится к алгоритмическим, решение должно укладываться по сложности в O(n).
Условие:
Дана строка содержащая скобки разных видов: '(, ), {, }, [, ]'. Необходимо определить является ли скобочная последовательность правильной, а именно:
- для каждой открывающей скобки есть закрывающая из той же пары, например, для открывающей '[' будет ']'
- скобки закрываются в правильном порядке, то есть не может быть так, что сначала идет закрывающая, а потом открывающая из той же пары
- пустая строка считается правильной
- в строке кроме скобок больше ничего не содержится. это условие может не соблюдаться, если на собесе захотят усложнить задачу
Начнем с тестовых кейсов, чтобы лучше понять условие:
- '' —> true (пустая строка)
- () —> true
- ()[]{} —> true
- ({}) —> true
- ][ —> false
- (} —> false
- {}) —> false
Как будем решать:
Вспоминаем такую структуру данных как стек, которая основывается на последовательности LIFO (Last In First Out).
- В цикле, если нам встречается открывающаяся скобка, то кладем ее на стек.
- Если встречается закрывающаяся скобка, то сравниваем ее с последним элементом в стеке, если скобки матчатся друг с другом (открывающая из стека равна соответствующей закрывающей), то вынимаем открывающую скобку из стека.
- Если скобки не совпадают, сразу возвращаем false из функции — последовательность неправильная.
- После завершения цикла проверяем, что стек пустой и все скобки совпали попарно. Если не пустой возвращаем false.
Реализация на Go
- В начале функции инициализируем мапу с парами скобок
- Далее создаем стек на основе слайса
- (Опционально) Проверяем, что в строке есть хотя бы две скобки
- Далее, в цикле реализован рассмотренный выше алгоритм
Код можно скопировать здесь
Реализация на Python
В питоне выглядит лаконичнее за счет наличия метода извлечения элемента из списка.
