Время O(n), дополнительная память O(n) в худшем случае. Каждый символ обрабатывается один раз, а каждая скобка добавляется и удаляется не более одного раза.
Какова сложность проверки сбалансированных скобок
Время O(n), дополнительная память O(n) в худшем случае. Каждый символ обрабатывается один раз, а каждая скобка добавляется и удаляется не более одного раза.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Условие
IsBalanced проходит строку длины n, складывает открывающие скобки в стек и проверяет закрывающие по вершине. Оцените время и дополнительную память.
Ответ
Время O(n), дополнительная память O(n) в худшем случае. Каждый символ обрабатывается один раз, а каждая скобка добавляется и удаляется не более одного раза.
Ранний выход при неправильной закрывающей скобке ускоряет отдельный пример, но не меняет худшую оценку. Для одного типа скобок достаточно счётчика и O(1) памяти. Для нескольких типов нужно помнить порядок вложенности: один общий баланс не отличит правильную строку от ([)].