Valid Parentheses Python Solution with Tests

LeetCode 20, Easy. Topics: String, Stack. View on LeetCode. Generate this problem as a practice environment: tested reference solution, 20 parametrized pytest cases, and a playground notebook:

lcpy gen -n 20   # by problem number
lcpy gen -s valid_parentheses   # by problem name

Problem

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

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

Examples

Input: s = "()"
Output: true

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

Input: s = "(]"
Output: false

Input: s = "([])"
Output: true

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

Constraints

1 <= s.length <= 10^4
s consists of parentheses only '()[]{}'.

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(n)
    # Space: O(n)
    def is_valid(self, s: str) -> bool:
        stack = []
        pairs = {"(": ")", "[": "]", "{": "}"}

        for char in s:
            if char in pairs:
                stack.append(char)
            elif not stack or pairs[stack.pop()] != char:
                return False

        return not stack

Complexity

Time	Space
O(n)	O(n)

Welcome

Getting Started

Practice

CLI

Catalog

Contributing

Troubleshooting

Valid Parentheses Python Solution with Tests

Problem

Examples

Constraints

Solution

Complexity

Tags

​Problem

​Examples

​Constraints

​Solution

​Complexity

​Tags

Problem

Examples

Constraints

Solution

Complexity

Tags