## DEV Community is a community of 665,832 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Day 20 - Valid Parentheses Ruairí O'Brien

## The Problem

Given a string `s` containing just the characters `'(', ')', '{', '}', '['` and `']'`, determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Example 1:

``````Input: s = "()"
Output: true
``````

Example 2:

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

Example 3:

``````Input: s = "(]"
Output: false
``````

Example 4:

``````Input: s = "([)]"
Output: false
``````

Example 5:

``````Input: s = "{[]}"
Output: true
``````

Constraints:

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

## Tests

``````import pytest
from .Day20_ValidParentheses import Solution

sol = Solution()

@pytest.mark.parametrize(
"s,expected",
[
("()", True),
("()[]{}", True),
("(]", False),
("([)]", False),
("{[]}", True),
("[", False),
("((", False),
],
)
def test_is_valid_parentheses(s, expected):
assert sol.isValid(s) == expected
``````

## Solution

``````class Solution:
def isValid(self, s: str) -> bool:
if len(s) == 1:
return False

stack = []
brackets = {"}": "{", ")": "(", "]": "["}
for b in s:
if b in brackets:
if len(stack) == 0 or stack.pop() != brackets[b]:
return False
else:
stack.append(b)

return len(stack) == 0
``````

## Analysis ## Commentary

This seems like a classic 'stack' problem to me. An opening bracket must be closed and they must be closed in reverse order of opening. We use a list as a stack there. When we encounter a closing bracket, pop the last bracket from the stack and see if it was the opening bracket for the current closing bracket.

e.g.

``````stack = ['(', '{']

bracket = '}'

stack.pop()
# '{'
``````

'{' and '}' match so we continue on to the next one. If they didn't, we return false.

We only ever put open brackets on the stack. We use a map to store the closing bracket to look up the respective closing bracket.

My solution didn't do great in terms of performance. Must have a think about it and see where it could be made faster but leaving it here for today.