DEV Community

Ruairí O'Brien
Ruairí O'Brien

Posted on

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
Enter fullscreen mode Exit fullscreen mode

Example 2:

Input: s = "()[]{}"
Output: true
Enter fullscreen mode Exit fullscreen mode

Example 3:

Input: s = "(]"
Output: false
Enter fullscreen mode Exit fullscreen mode

Example 4:

Input: s = "([)]"
Output: false
Enter fullscreen mode Exit fullscreen mode

Example 5:

Input: s = "{[]}"
Output: true
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Analysis

Alt Text

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()
# '{'
Enter fullscreen mode Exit fullscreen mode

'{' 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.

Image of Datadog

The Essential Toolkit for Front-end Developers

Take a user-centric approach to front-end monitoring that evolves alongside increasingly complex frameworks and single-page applications.

Get The Kit

Top comments (0)

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up