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

Напишите функцию is_valid(s), которая проверяет корректность последовательности из скобок трёх видов (), [], {}: каждая открывающая закрывается той же парой в правильном порядке. Пустая строка корректна.

Корректные: (()), ()(), (()()). Некорректные: (, )(, ((), ([)].

КАК СПРАШИВАЮТ«Дефолтная задача с LeetCode», как её называют сами интервьюеры. Ждут стек и словарь пар, O(n). Дополнительно спрашивают про перекрёстный случай `([)]` и про пустой стек при закрывающей скобке.

ПОДСКАЗКА

Стек: открывающие кладём, для закрывающей проверяем, что стек не пуст и на вершине парная скобка. В конце стек должен быть пустым.

РЕШЕНИЕ И РАЗБОР

Сначала попробуйте сами: на собеседовании подсказки не будет.

Стек: открывающие скобки кладём, для закрывающей проверяем, что стек не пуст и наверху парная открывающая, и снимаем её. Словарь «закрывающая → открывающая» избавляет от трёх if.

Два крайних случая, на которых ловят: закрывающая при пустом стеке ()() и непустой стек в конце ((()). Посторонний символ по условию делает строку некорректной.

def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in pairs.values():
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
        else:
            return False
    return not stack

ментор разберёт с вами

песочница · Pythonрешено 0 / 1

Ctrl+Enter

ТЕСТЫ

Ввод	Ваш вывод	Ожидаемый вывод
"(())"	—	True
"()()"	—	True
"(()())"	—	True
"("	—	False
")("	—	False
"(()"	—	False
"([)]"	—	False
"{[()]}"	—	True
скрытый тест 9
скрытый тест 10

решённые задания сохранятся в прогресс после входа

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

Корректные: (()), ()(), (()()). Некорректные: (, )(, ((), ([)].

ПОДСКАЗКА

РЕШЕНИЕ И РАЗБОР

Сначала попробуйте сами: на собеседовании подсказки не будет.

def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in pairs.values():
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
        else:
            return False
    return not stack

ментор разберёт с вами

Ввод

Ваш вывод

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

"(())"

—

True

"()()"

—

True

"(()())"

—

True

"("

—

False

")("

—

False

"(()"

—

False

"([)]"

—

False

"{[()]}"

—

True

скрытый тест 9

скрытый тест 10