(LeetCode) 20. Valid Parentheses

20. Valid Parentheses

• Explore : Interview > Top Interveiw Questions > Easy Collection
• 분류 : Others
• 난이도 : Easy

Problem

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

Input: s = "()"
Output: true

Example 2

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

Example 3

Input: s = "(]"
Output: false

Example 4

Input: s = "([)]"
Output: false

Example 5

Input: s = "{[]}"
Output: true

Constraints

• 1 <= s.length <= 10^4
• s consists of parentheses only '()[]{}'.

Solution

Exapnder

class Solution {
    fun isValid(s: String): Boolean {
        if (s.length % 2 == 1) {
            return false
        }
        var stack = Stack<Char>()
        s.forEach {
            if (it == '(' || it == '{' || it == '[') {
                stack.push(it)
            } else {
                if (stack.isEmpty()) {
                    return false
                }
                if (it == ')' && stack.peek() == '(') {
                    stack.pop()
                }
                else if (it == '}' && stack.peek() == '{') {
                    stack.pop()
                }
                else if (it == ']' && stack.peek() == '[') {
                    stack.pop()
                } else {
                    return false
                }
            }
        }
        return stack.isEmpty()
    }
}

Point of Thinking

• 전형적인 Stack 활용 문제이다. 이른바 괄호 검사 문제.
• 괄호 검사 문자는 주어진 문자열이 짝수가 아니면 무조건 false이므로 전방 예외 처리를 한다.
• (, {, [ 면 무조건 스택에 푸시한다.
• ), }, ] 면 아래 절차를 수행한다.
  • stack이 비어있다면 false이다. EmptyStackException을 활용하는 것도 방법.
  • stac이 비어있지 않다면 닫힌 괄호에 대응하는 열린 괄호가 맞는 지 peek()을 통해 확인한다.
  • peek()을 통해 확인한 열린 괄호가 닫힌 괄호와 Pair라면 pop() 아니라면 false를 반환한다.
  • 문자열 순회 후 stack이 비어있다면 true, 아니면 false를 반환한다.
• 위의 조건들로 처리하면 Accepted.