# 0020. Valid Parentheses

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Valid Parentheses](https://leetcode.com/problems/valid-parentheses/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0020-valid-parentheses)

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.**
   {% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

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

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

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

Input: s = "(]"
Output: false

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

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

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
Use the **hash table to record the mapping of parentheses** and the **stack to store left-side parenthesis** for further verification when meeting right-side parenthesis.
{% endhint %}

* return False **if first char is a right-side parenthesis**
* return False **if the stack is already empty but there is an incoming parenthesis**
* return False **if the incoming parenthesis doesn't match with the popped item**

**Note** that **we need to check whether the stack is empty** before returnning the answer.\
If the stack is not empty but there are no incoming parentheses, return False.
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
class Solution:
    def isValid(self, s: str) -> bool:
        # (base case)fy
        if len(s) == 1: return False
        
        # ==================================================
        #  String + Stack                                  =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        table = { 
            ')': '(', 
            ']': '[', 
            '}': '{' 
        }
        stack = []
        
        # return False if first char is right-side parenthesis
        if s[0] in table: return False
        
        for char in s:
            if char in table:
                # return False if stack is already empty
                if not stack: return False 
                
                if stack.pop() != table[char]: return False
                
            else:
                stack.append( char )
                
        # check stack's capacity before returning True
        return not stack
```

{% endtab %}

{% tab title="🤖 Java" %}

```java
class Solution {
    /**
     * @time  : O(n)
     * @space : O(n)
     */
     
    public boolean isValid(String s) {
        /* base case */
        if(s.length() == 1) return false;
        
        HashMap<Character, Character> table = new HashMap<Character, Character>();
        table.put( ')', '(' );
        table.put( '}', '{' );
        table.put( ']', '[' );
        
        if( table.containsKey( s.charAt(0) ) ) return false;
        
        Stack<Character> stack = new Stack<Character>();
        
        for(int i=0 ; i<s.length() ; i++) {
            char c = s.charAt(i);
            
            if(table.containsKey(c)){
                if(stack.isEmpty()) return false;
                
                char top = stack.pop();
                
                if(top != table.get(c)) return false;
                
            } else{
                stack.push(c);
            }
        }
        
        return stack.isEmpty();
    }
}
```

{% endtab %}
{% endtabs %}