Ответ
Для решения задачи Valid Parentheses можно использовать стек. Алгоритм проверяет, что каждая открывающая скобка имеет соответствующую закрывающую в правильном порядке.
fun isValid(s: String): Boolean {
val stack = ArrayDeque<Char>()
val map = mapOf(')' to '(', ']' to '[', '}' to '{')
for (char in s) {
if (map.containsValue(char)) {
stack.push(char)
} else if (map.containsKey(char)) {
if (stack.isEmpty() || stack.pop() != map[char]) {
return false
}
}
}
return stack.isEmpty()
}
Алгоритм:
- Идем по строке символ за символом
- Если встречаем открывающую скобку - кладем в стек
- Если встречаем закрывающую - проверяем, что стек не пуст и верхний элемент стека - соответствующая открывающая скобка
- В конце проверяем, что стек пуст (все скобки закрыты)
Сложность: O(n) по времени и O(n) по памяти.