Day 20 - Valid Parentheses

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

Link to code

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

Link to code

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.