Валидация скобочной последовательности

#kotlin #algorithms #leetcode #easy

Давайте разберем популярную задачу валидации скобочной последовательности.
Ее можно найти вот здесь Valid Parentheses

Постановка задачи

Дана некоторая строка, содержащая символы '(', ')', '{', '}', '[' и ']'. Необходимо определить, является ли данная строка валидной скобочной последовательностью.

Скобочная последовательность является валидной при выполнении двух условий:

Открывающие скобки закрываются скобками того же типа
Открывающие скобки закрываются в правильном порядке

Примеры входных данных

Пример 1

() - данная строка является правильной скобочной последовательностью, так как выполняются условия 1 и 2

Пример 2

()[]{} - данная строка является правильной скобочной последовательностью, так как выполняются условия 1 и 2

Пример 3

([]) - данная строка является правильной скобочной последовательностью, так как выполняются условия 1 и 2

Пример 4

([]} - данная строка не является правильной скобочной последовательностью, так как не выполняется первое условие

Пример 5

({)} - данная строка не является правильной скобочной последовательностью, так как не выполняется второе условие

Решение

Первой идеей может быть сделать подсчет количества открывающих и закрывающих скобок. Но тогда мы можем не удовлетворить второму условию. Поэтому порядок нам тоже важен. Для этого нам надо выбрать структуру стек. Мы будем складывать в него открывающие скобки, а при встрече закрывающих - доставать их.

Для стека нам подойдет класс ArrayDeque, это реализация двухсторонней очереди.

Решение по шагам

1) Достаем очередной элемент из строки. Для этого итерируемся по строке с помощью конструкции forEach. Каждый элемент в итерации будет иметь тип Char.

s.forEach { char ->
    ...
}

2) Проверяем, является ли он открывающей или закрывающей скобкой. Для этого мы используем конструкцию when
3) Если скобка открывающая, то кладем в стек

...
when(char) {
    '(' -> stack.addLast(char)
    '[' -> stack.addLast(char)
    '{' -> stack.addLast(char)
    ...
}
...

4) Если скобка закрывающая, то достаем скобку из стека и сравниваем на соответствие
5) Если скобки соответствуют, то итерируемся дальше
6) Если скобки не соответствуют, то возвращаем false

when(char) {
    ...
    else -> if (stack.isNotEmpty() || isCorrectChar(stack.removeLast())) return false
}
...

7) В конце возвращаем true, если стек пустой, и false, если в стеке остались элементы

return stack.isEmpty()

Оптимизация

Поскольку мы кладем в стек открывающую скобку, возникает необходимость сравнения на соответствие с закрывающей. Получается весьма громоздкая конструкция, которую надо поддерживать. Вместо этого можно сразу класть в стек соответствующую закрывающую скобку, а затем сравнивать на равенство.

when(char) {
    '(' -> stack.add(')')
    '[' -> stack.add(']')
    '{' -> stack.add('}')
}

Оценка сложности

По времени - O(s.length). Мы циклом проходимся по всей строке, что дает нам O(s.length). Так же мы используем операции вставки и извлечения в конец двухсторонней очереди, что дает O(1).
По памяти - O(s.length). Максимальный размер дополнительно используемой памяти - O(s.length), так как в стэк мы не добавляем больше длины входных данных.

Полное решение

fun isValid(s: String): Boolean {
    val stack = ArrayDeque<Char>()
    s.forEach { char ->
        when(char) {
            '(' -> stack.addLast(')')
            '[' -> stack.addLast(']')
            '{' -> stack.addLast('}')
            else -> if (stack.isNotEmpty() || stack.removeLast() != char) return false
        }
    }
    return stack.isEmpty()
}