LeetCode Entry

20. Valid Parentheses

10.04.2023 medium 2023 kotlin

use HashMap to check matching bracket.

20. Valid Parentheses medium

fun isValid(s: String): Boolean = with(Stack<Char>()) {
    val opened = hashSetOf('(', '[', '{')
    val match = hashMapOf(')' to '(' , ']' to '[', '}' to '{')
    !s.any { c ->
        when {
            c in opened -> false.also { push(c) }
            isEmpty() -> true
            else -> pop() != match[c]
        }
    } && isEmpty()
}

blog post

Join me on Telegram

telegram

Intuition

Walk the string and push brackets to the stack. When bracket is closing, pop from it.

Approach

• use HashMap to check matching bracket.

  Complexity

• Time complexity: \(O(n)\)
• Space complexity: \(O(n)\)