Easystackparentheses
Как проверить правильность скобок?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
LeetCode 20. Стек для matching brackets: для каждой закрывающей проверяем top стека. O(n) время, O(n) память.
def isValid(s):
stack = []
pairs = {')': '(', ']': '[', '}': '{'}
for c in s:
if c in pairs.values(): # открывающая
stack.append(c)
elif c in pairs: # закрывающая
if not stack or stack[-1] != pairs[c]:
return False
stack.pop()
return not stackВариации: Generate Parentheses (backtracking), Longest Valid Parentheses (stack с индексами или DP), Min Add to Make Valid (счётчик open). Для single типа скобок — счётчик balance O(1) space. Стек — универсальная структура для nested/matching problems.
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.