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()
Source link
lol
