20.valid-parentheses

Constraints

1. 1 <= s.length <= 104
2. s consists of parentheses only '()[]{}'.

Idea #1 (Time: N, Memory: N)

1. when buf is not empty, iterate each character
2. if head is None or different type with token, push
3. if pair, pop head
4. if buf and stack is empty, return true, else return false

Idea #2 (Time: N, Memory: N)

Test Cases

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Example 4:

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

Code

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack:
    def __init__(self):
        self.top = None

    def push(self, data):
        if self.top is None:
            self.top = Node(data)
        else:
            node = Node(data)
            node.next = self.top
            self.top = node

    def pop(self):
        if self.top is None:
            return None
        node = self.top
        self.top = self.top.next
        return node.data

    def peek(self):
        if self.top is None:
            return None
        return self.top.data

    def is_empty(self):
        return self.top is None

class Solution:
    def isValid(self, s: str) -> bool:
        pair = {
            ')': '(',
            '}': '{',
            ']':'['
        }
        mystack = Stack()
        for c in s:
            if mystack.is_empty() or c not in pair.keys() or pair[c] != mystack.peek():
                mystack.push(c)
            elif pair[c] == mystack.peek():
                mystack.pop()
        return mystack.is_empty()