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

#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()
}

Build apps, not infrastructure.

Dealing with servers, hardware, and infrastructure can take up your valuable time. Discover the benefits of Heroku, the PaaS of choice for developers since 2007.

Visit Site