Валидация скобочной последовательности
Tags: kotlin, algorithms, leetcode, easy
Published: 2022-08-22 13:15:00

Давайте разберем популярную задачу валидации скобочной последовательности.
Ее можно найти вот здесь [Valid Parentheses](https://leetcode.com/problems/valid-parentheses/)

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

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

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

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

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

Для стека нам подойдет класс [ArrayDeque](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/-array-deque/), это реализация двухсторонней очереди.

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

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

```kotlin
s.forEach { char ->
    ...
}
```
2) Проверяем, является ли он открывающей или закрывающей скобкой. Для этого мы используем конструкцию when
3) Если скобка открывающая, то кладем в стек

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

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

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

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

```kotlin
return stack.isEmpty()
```

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

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

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

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

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

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

```kotlin
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()
}
```