Valid Parentheses - Solution
Solutions and explanations
Video Explanation
class Solution:
def isValid(self, s: str) -> bool:
cur_str = s
while "()" in cur_str or "{}" in cur_str or "[]" in cur_str:
cur_str = cur_str.replace("()", "")
cur_str = cur_str.replace("{}", "")
cur_str = cur_str.replace("[]", "")
return cur_str == ""
Complexity Analysis
Here, n is the input size.
- Time Complexity:
O(n²) - Space Complexity:
O(n)
class Solution:
def isValid(self, s: str) -> bool:
bracket_map = { "]": "[", ")": "(", "}": "{"} # close -> open
open_bracket_stack = []
for ele in s:
if ele in bracket_map: # close
if open_bracket_stack and open_bracket_stack[-1] == bracket_map[ele]:
open_bracket_stack.pop()
else:
return False
else:
open_bracket_stack.append(ele) # open
return not open_bracket_stack
Complexity Analysis
Here, n is the input size.
- Time Complexity:
O(n) - Space Complexity:
O(n)