20. Valid Parentheses

Posted on | In |
  • Source : Link
  • Author : Han
  • Date : 2022-02-10

Problems

Given a string s containing just the characters '(', ')', '{', '}', '['and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

Example 1:

1
2
3
Input: s = "()"
Output: true

Example 2:

1
2
3
Input: s = "()[]{}"
Output: true

Example 3:

1
2
3
Input: s = "(]"
Output: false

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.*

class Solution {
    private val prefix = arrayListOf("(", "{", "[")
    private val suffix = arrayListOf(")", "}", "]")

    fun isValid(s: String): Boolean {
        val stack = Stack<String>()
        s.forEachIndexed { _, c ->
            val str = c.toString()
            when {
                this.isPrefix(str) -> stack.push(str)
                this.isSuffix(str) -> if (stack.isEmpty() || !this.isMatch(stack.pop(), str)) return false
            }
        }

        when {
            stack.isNotEmpty() -> return false
        }
        return true
    }


    private fun isPrefix(string: String): Boolean {
        return prefix.any { it == string }
    }

    private fun isSuffix(string: String): Boolean {
        return suffix.any { it == string }
    }

    private fun isMatch(pre: String, suf: String): Boolean {
        return prefix.indexOf(pre) == suffix.indexOf(suf)
    }
}