Valid Parentheses

Stack의 appned, pop 연산은 O(1)의 시간복잡도를 갖는다.

---

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

class Solution {
    func isValid(_ s: String) -> Bool {
        var stack: [String] = []
        for input in s {
            if input == "(" {
                stack.append(")")
            } else if input == "[" {
                stack.append("]")
            } else if input == "{" {
                stack.append("}")
            } else if stack.isEmpty {
                return false
            } else if let validValue = stack.popLast(), validValue != String(input) {
                print(validValue, input, validValue == String(input))
                return false
            }
        }
        return stack.isEmpty

    }
}

제약조건
1 <= s.length <= 10^4

---

stack의 경우 list로 구현되어 있고, random access가 가능하여 O(1)의 시간복잡도를 갖고있는 메서드 사용, n번 만큼 for문을 수행함으로, O(n) 시간복잡도를 갖는다.