Valid Parentheses
Statement
Given a string that consists of opening and closing parentheses, find whether or not the string contains valid parentheses: every opening parenthesis is closed by the same kind of parenthesis, and every opening parenthesis must be closed in the correct order.
Constraints
- 1 ≤
s.length()≤ 10³
Solution
"""
production algorithm
"""
from data_structures.stack.stack import Stack
class Solution:
def is_valid(self, s):
"""
time complexity O(n)
space complexity O(n)
"""
stack = Stack()
for c in s:
if not stack.empty() and \
(stack.top() == "(" and c == ")") or \
(stack.top() == "[" and c == "]") or \
(stack.top() == "{" and c == "}"):
stack.pop()
else:
stack.push(c)
return stack.empty()"""
unit tests
"""
from unittest import TestCase
from algorithms.stacks.valid_parentheses.solution import Solution
class SolutionTestCase(TestCase):
def test_all_valid_parentheses(self):
# Given
string = "{[(()[]{})]}"
solution = Solution()
# When
actual = solution.is_valid(string)
# Then
expected = True
self.assertEqual(actual, expected)
def test_some_invalid_parentheses(self):
# Given
string = "}])()[]{}([{"
solution = Solution()
# When
actual = solution.is_valid(string)
# Then
expected = False
self.assertEqual(actual, expected)Strategy
Stacks.
Explanation
A stack is used to hold opening parentheses that haven’t been closed yet. Then, the characters of the string are iterated. If the top of the stack is some kind of opening parenthesis, and the current character of iteration is the same kind of closing parenthesis, then the top of the stack is popped. Otherwise, the current character of iteration is pushed to the top of the stack.
At the end of iteration, if the stack is empty, then the string contains valid parentheses. Otherwise, the stack isn’t empty, and so the string doesn’t contain valid parentheses. The reason is that in a string that contains valid parentheses, every opening and closing parenthesis of the same kind stay out of the stack.
Time Complexity
The time complexity of the algorithm is O(n), where n is the number of characters in the string.
Space Complexity
At worst, the stack grows to the size of the string. Therefore, the auxiliary space complexity of the algorithm is O(n).
