Валидные скобки
Дана строка s, состоящая из следующих символов: '(', ')', '{', '}', '[' и ']'.
Строка s является валидной, если:
- Каждая открытая скобка закрыта скобкой того же типа.
- Открытые скобки закрыты в правильном порядке.
- Каждая закрытая скобка имеет соответствующую открытую скобку того же типа.
Верните true, если строка s валидна, и false в противном случае.
Пример 1:
Input: s = "()" Output: true <br> **Пример 2:** ```java Input: s = "()[]{}" Output: true
Пример 3:
Input: s = "(]" Output: false
Рекомендуемая временная и пространственная сложность
Вам следует стремиться к решению с временной сложностью O(n) и пространственной сложностью O(n), где n — длина входной строки.
Подсказка 1
Решение грубой силы заключалось бы в проверке каждой скобки по отношению к каждой другой скобке в строке. Это было бы решение с временной сложностью O(n^2). Можете ли вы придумать более эффективный способ?
Подсказка 2
Можно ли использовать структуру данных, которая позволяет эффективно проверять, является ли скобка закрывающей и соответствует ли она последней открытой скобке?
Подсказка 3
Мы можем использовать стек для хранения открытых скобок. Когда мы встречаем закрывающую скобку, мы проверяем, соответствует ли она последней открытой скобке в стеке.