:orphan:

Valid Parentheses
=================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/valid-parentheses/

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.

 

**Example 1:**

.. container:: example-block

   **Input:** s = "()"

   **Output:** true

**Example 2:**

.. container:: example-block

   **Input:** s = "()[]{}"

   **Output:** true

**Example 3:**

.. container:: example-block

   **Input:** s = "(]"

   **Output:** false

**Example 4:**

.. container:: example-block

   **Input:** s = "([])"

   **Output:** true

**Example 5:**

.. container:: example-block

   **Input:** s = "([)]"

   **Output:** false

 

**Constraints:**

- ``1 <= s.length <= 10``\ :sup:```4```
- ``s`` consists of parentheses only ``'()[]{}'``.

.. highlight:: python

Pattern
-------
String, Stack

Solution
--------
This is a classic use case for stacks. For each opening parenthesis, push it
onto the stack. For each closing parenthesis, pop the stack and check if the
popped parenthesis belongs with the closing parenthesis. If it doesn't, return
False. At the end, the stack should be empty for the string to be valid.

Code
----

.. literalinclude:: ../problems/easy/valid-parentheses/valid_parentheses__approach_1.py
    :language: python
    :lines: 12-

Test
----
>>> from valid_parentheses__approach_1 import isValid
>>> isValid('()')
True
>>> isValid('()[]{}')
True
>>> isValid('(]')
False

Complexity
----------
| :math:`n` is the length of ``s``.
| Time: :math:`O(n)` — single pass through ``s``.
| Auxiliary Space: :math:`O(n)` — stack

.. autofunction:: valid_parentheses__approach_1.isValid

.. autofunction:: valid_parentheses__approach_1.parentheses_match