Как решить задачу Valid Parentheses с LeetCode

«Как решить задачу Valid Parentheses с LeetCode» — вопрос из категории Алгоритмы и структуры данных, который задают на 23% собеседований Android Разработчик. Ниже — развёрнутый ответ с разбором ключевых моментов.

Ответ

Для решения задачи 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()
}

Алгоритм:

  1. Идем по строке символ за символом
  2. Если встречаем открывающую скобку - кладем в стек
  3. Если встречаем закрывающую - проверяем, что стек не пуст и верхний элемент стека - соответствующая открывающая скобка
  4. В конце проверяем, что стек пуст (все скобки закрыты)

Сложность: O(n) по времени и O(n) по памяти.