leetcode: 20. Valid Parentheses

문제링크

풀이1

• 문자열의 문자를 순회한다.
• 문자가 (, [, { 라면 스택에 push한다.
• 문자가 ), ], } 일 때 스택이 비어있으면 false를 반환하고, 스택의 pop값이 원하는 값이 아니라면 false를 반환한다.
• 순회를 마치고 다시 한번 스택이 비어있는지 검사한다.

class Solution {
    fun isValid(s: String): Boolean {
        val stack = mutableListOf<Char>()
        for (i in 0 until s.length) {
            when (s[i]) {
                '(' -> stack.add('(')
                '[' -> stack.add('[')
                '{' -> stack.add('{')
                ')' -> {
                    if (stack.isEmpty()) return false
                    if (stack.last() != '(') return false
                    stack.removeAt(stack.size - 1)
                }
                ']' ->{
                    if (stack.isEmpty()) return false
                    if (stack.last() != '[') return false
                    stack.removeAt(stack.size - 1)
                }
                '}' ->{
                    if (stack.isEmpty()) return false
                    if (stack.last() != '{') return false
                    stack.removeAt(stack.size - 1)
                }
            }
        }
        if (stack.isNotEmpty()) return false
        return true
    }
}

시간복잡도 : O(N)
공간복잡도 : O(N)

풀이2

• 위의 풀이 방법과 거의 동일하다.
• 단, 문자가 (, [, { 일 때 해당 문자의 대응하는 문자를 스택에 push한다.
• 문자가 ), ], } 일 때 스택이 비어 있거나 스택의 pop값과 동일하지 않다면 false를 반환한다.

class Solution {
    fun isValid(s: String): Boolean {
        val stack = mutableListOf<Char>()
        for (i in 0 until s.length) {
            when (s[i]) {
                '(' -> stack.add(')')
                '[' -> stack.add(']')
                '{' -> stack.add('}')
                else -> {
                    if (stack.isEmpty() || stack.removeAt(stack.size - 1) != s[i]) {
                        return false
                    }
                }
            }
        }
        if (stack.isNotEmpty()) return false
        return true
    }
}

시간복잡도 : O(N)
공간복잡도 : O(N)