> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://r24zeng.gitbook.io/leetcode-notebook/zhong-yu-shua-dao-100-dao-le-wo-shi-fen-shui-ling/bu-chong-120-dao/20.-valid-parentheses.md).

# 20. Valid Parentheses

\# Easy

{% hint style="info" %}
知道就是知道，不知道就是不知道

Store `(open_braket, close_braket)` pair in mapping, to match each braket.

Use stack to ensure correct order, if it's an open braket, then add to stack, if it's a close braket, then pop out from stack.

Two true-false check:

1. check if stack is empty, then can't check last element of stack with new coming element.
2. check if stack is empty at the end, which means must ensure all open braket are closed.
   {% endhint %}

{% tabs %}
{% tab title="Python" %}

```python
class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        # edge case
        if len(s)%2 != 0: # odd, then must be false
            return False
        
        # regular case
        dic = {'(': ')', '[': ']', '{': '}'}
        left = set(['(', '[', '{'])
        stack = []
        for item in s:
            if item in left:
                stack.append(item)
            elif stack and item == dic[stack[-1]]:
                stack.pop()
            else:
                return False
            
        return stack == []
```

{% endtab %}
{% endtabs %}

Time complexity = $$O(n)$$ , space comlexity = $$O(n)$$