> For the complete documentation index, see [llms.txt](https://joshualbarb.gitbook.io/leetcode-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://joshualbarb.gitbook.io/leetcode-problems/stack/valid-parentheses.md).

# Valid Parentheses

## 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.

**Constraints:**

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

{% hint style="info" %}
For example:

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

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

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

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

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

{% endhint %}

### Thought Process

* This is a stack problem because we need to check when we come across a closing bracket, if the previous element was an opening bracket. Since stacks can keep track of the last viewed element, a stack is perfect for this scenario.&#x20;

* We need to use a stack to make sure the previous viewed element is an opening bracket whenever we come across a closing bracket. This is because there always needs to be an opening bracket to a closing bracket.

* We check if brackets are the same type by using a dictionary.

## Solution

```
class Solution:
    def isValid(self, s: str) -> bool:
        
        openBrackets = "({["
        closingBrackets = ")}]"
        matchingBrackets = {")":"(", "]":"[", "}":"{"}
        stack = []
        
        for char in s:
            if char in openBrackets:
                stack.append(char)
            elif char in closingBrackets:
                if not stack: #case2: empty stack but closing brackets
                    return False
                elif matchingBrackets[char] == stack[-1]: #if top of stack is matching bracket
                    stack.pop()
                else: #case 3: mismatching brackets
                    return False
                
        return (stack) == 0
        
```

## Time Complexity

* **Time:** O(n)
* **Space:** O(n)