Valid Parentheses

Q: Какова временная сложность задачи «Правильные скобки»?

Решение со стеком выполняется за время O(n) , поскольку каждый символ добавляется в стек или извлекается из него не более одного раза. В худшем случае оно использует O(n) памяти — для строки, состоящей только из открывающих скобок. Многократное удаление совпадающих пар занимает время O(n²) , поскольку из глубоко вложенной строки за один проход удаляется только одна пара.

ЛегкоСтек

+10

Дана строка s, состоящая только из символов скобок (, ), [, ], { и }. Верните true, если скобки сбалансированы: каждая закрывающая скобка закрывает последнюю из ещё открытых скобок, они одного типа, и в конце не остаётся незакрытых скобок. В противном случае верните false.

Функция

isValid(s: string) → boolean

sstring: строка скобок для проверки
Возвращаетboolean: сбалансированы ли скобки

Ограничения

1 ≤ s.length ≤ 10⁴
s содержит только символы (, ), [, ], { и }.

Примеры

Ввод: s = "[]{}()"
Вывод: true
Пояснение: Три пары стоят рядом, и каждая закрывается сразу после того, как открывается.

Ввод: s = "{(})"
Вывод: false
Пояснение: Символ } появляется, пока открытая после него ( всё ещё не закрыта, поэтому он закрывает скобку неправильного типа.

Дополнительный вопрос

Если бы строка содержала только круглые скобки, можно было бы проверить её с помощью одного счётчика вместо стека, используя дополнительную память O(1)?

Решение

Подсчета скобок недостаточно: {(}) содержит по одной открывающей и закрывающей скобке каждого вида, но всё равно некорректна, потому что важен порядок. Стек хранит ещё не закрытые скобки в порядке их открытия, поэтому одного прохода со стеком достаточно, чтобы определить, корректна ли вся строка.

Повторно удаляйте совпадающие пары

Верно, но не успевает на самых больших тестах

Идея

У каждой сбалансированной строки есть самая внутренняя пара скобок, между которыми ничего нет, например () внутри {[()]}. Удаление соседней совпадающей пары никогда не меняет того, является ли строка сбалансированной. Поэтому повторяй удаления, пока очередной проход не перестанет удалять символы: сбалансированная строка станет пустой, а несбалансированная застрянет с оставшимися символами, как {(}) с самого начала.

В каждом проходе сканируется вся строка и создаётся её новая копия, а вложенная строка вроде (((...))) теряет одну пару за проход. Это до n/2 проходов по O(n) операций, то есть всего O(n²).

Алгоритм

Удаляй из строки все (), [] и {}.
Если за этот раунд ничего не было удалено, остановись.
Иначе повтори с укороченной строкой.
Верни true, если строка в итоге стала пустой, и false, если осталась хотя бы одна скобка.

def isValid(s):
    while True:
        # Delete every adjacent matched pair in one round.
        shorter = s.replace("()", "").replace("[]", "").replace("{}", "")
        if shorter == s:
            break  # nothing left to delete
        s = shorter
    return s == ""

Один проход со стеком

Идея

Закрывающая скобка должна закрывать ту скобку, которая была открыта последней и всё ещё остаётся открытой. Последней открытая скобка закрывается первой, и именно такой порядок «последним вошёл — первым вышел» поддерживает стек.

Добавляй в стек закрывающую скобку, которую ожидает каждая открывающая. Затем закрывающая скобка должна совпадать с верхним элементом стека. Пустой стек означает, что закрывать нечего; если верхний элемент другой, то закрывается скобка неверного типа, как это происходит с } в {(}), когда сверху находится ). В конце всё, что осталось в стеке, как в ((, было открыто, но так и не закрыто. Каждый символ добавляется в стек или извлекается из него один раз: время O(n) и не более n элементов в стеке.

Алгоритм

Создай пустой стек.
Для открывающей скобки помести в стек соответствующую ей закрывающую скобку.
Для закрывающей скобки верни false, если стек пуст или его верхний элемент — другой символ; в противном случае извлеки элемент из стека.
После последнего символа верни true, только если стек пуст.

def isValid(s):
    closers = {'(': ')', '[': ']', '{': '}'}
    stack = []
    for ch in s:
        if ch in closers:
            stack.append(closers[ch])
        elif not stack or stack.pop() != ch:
            return False
    return not stack

Ловушки и крайние случаи

Подсчёт каждого вида скобок. {(}) имеет одинаковое количество открывающих и закрывающих скобок, но всё равно является недопустимой строкой, а )( недопустима только из-за порядка скобок.
Извлечение элемента из пустого стека. Строка, которая начинается с закрывающей скобки, например } или )]}, должна возвращать false, а не приводить к сбою.
Пропуск заключительной проверки. В строке (([{ нет неправильной закрывающей скобки, поэтому недопустимость строки показывает только оставшийся в стеке элемент.
Доверие к длине. Строка нечётной длины всегда недопустима, но чётная длина ничего не доказывает: (] и ())( недопустимы.
При подходе с удалением — передача скобок в регулярное выражение или шаблон Lua без экранирования. Там ( и [ имеют специальное значение; используйте замену обычного текста.

Частые вопросы3

Какова временная сложность задачи «Правильные скобки»?

Решение со стеком выполняется за время O(n), поскольку каждый символ добавляется в стек или извлекается из него не более одного раза. В худшем случае оно использует O(n) памяти — для строки, состоящей только из открывающих скобок. Многократное удаление совпадающих пар занимает время O(n²), поскольку из глубоко вложенной строки за один проход удаляется только одна пара.

Почему для задачи проверки корректности скобок используется стек?

Скобки могут быть вложенными, поэтому скобка, открытая последней, должна закрыться первой. Стек хранит эту скобку сверху, откуда её можно прочитать и удалить за постоянное время, что позволяет выполнить всю проверку за O(n).

Пустая строка — это допустимая последовательность скобок?

Да. В пустой строке нет незакрытых скобок, поэтому она сбалансирована: стек остается пустым, и циклу удаления нечего удалять. В этой задаче s всегда содержит хотя бы один символ.

def isValid(s):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

s = "[]{}()"

Ожидаемый вывод

true