Дана строка, в которой встречаются скобки трёх видов: (), [], {}.
Определите, правильно ли расставлены скобки:
- каждая открывающая скобка закрывается скобкой того же типа;
- скобки закрываются в правильном порядке (
([)] — неправильно);
- каждой закрывающей скобке соответствует открывающая.
Все остальные символы (буквы, пробелы, эмодзи — любые символы Unicode) не являются
скобками и игнорируются.
// IsValid сообщает, правильно ли расставлены скобки в s.
func IsValid(s string) bool
Примеры
IsValid("{[()()]}") // true
IsValid("([)]") // false
IsValid("(()())()") // true
IsValid(")()(") // false
IsValid("") // true
IsValid("f(a[i]) {}") // true
IsValid("(😀]") // false
Ограничения: 0 <= len(s) <= 10^6 байт. Решение — за линейное время: тест с глубокой
вложенностью на миллион символов не пропустит «удаляем () пока удаляется».
Устно: будет ли проблемой, если в строке встретятся эмодзи или кириллица?
Что изменится, если перебирать строку по байтам, а не по рунам?
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.