Проверьте, что строка скобок ()[]{} сбалансирована
Реализуйте isValid(s) для строки из символов ()[]{}. Верните true, если каждая открывающая скобка закрыта скобкой того же типа и в правильном порядке. Требования: O(n) по времени. Обработайте крайние случаи — закрывающая при отсутствии открытых (например "]") невалидна, и оставшиеся незакрытые открывающие в конце (например "(") тоже невалидны.
func isValid(s string) bool {
// ваш код здесь
return false
}Допишите реализацию.
Каждую открывающую скобку кладём в стек; на закрывающей делаем pop и проверяем, что она парная — выходим сразу при несовпадении или пустом стеке. Строка валидна, только если все закрывающие совпали и стек пуст в конце. Работает за O(n) по времени и O(n) по памяти.
- ✗Вернуть true в конце, не проверив, что стек пуст — остаются незакрытые открывающие
- ✗Сделать pop из пустого стека, когда первой идёт закрывающая, что вызывает panic по индексу
- ✗Сравнивать закрывающую с закрывающей вместо сопоставления каждой закрывающей с ожидаемой открывающей
- →Как доработать это, чтобы сообщать индекс первой непарной скобки?
- →Почему ранний выход при несовпадении сохраняет худший случай на уровне O(n)?
Задача
На вход подаётся строка из символов ()[]{}. Строка валидна, если каждая открывающая скобка закрыта скобкой того же типа и в правильном порядке.
// "[]({})" — валидная
// "[]{(})" — невалидная
func isValid(s string) bool {
// Закрывающая → ожидаемая открывающая.
pairs := map[byte]byte{')': '(', ']': '[', '}': '{'}
stack := make([]byte, 0, len(s))
for i := 0; i < len(s); i++ {
c := s[i]
if open, isCloser := pairs[c]; isCloser {
// На закрывающей: стек не пуст и вершина — парная открывающая.
if len(stack) == 0 || stack[len(stack)-1] != open {
return false
}
stack = stack[:len(stack)-1] // pop
} else {
stack = append(stack, c) // push открывающей
}
}
return len(stack) == 0 // все закрыты
}Ключевые инварианты: ранний выход при несовпадении, проверка пустоты стека перед pop и финальная проверка len(stack) == 0. Сложность — O(n) по времени и O(n) по памяти.
