Constraints
- 1 <= s.length <= 104
- s consists of parentheses only '()[]{}'.
Idea #1 (Time: N, Memory: N)
- when buf is not empty, iterate each character
- if head is None or different type with token, push
- if pair, pop head
- 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() 
Top comments (0)