## 20. Valid Parentheses

>[20. Valid Parentheses
](https://leetcode.com/problems/valid-parentheses/)

<br>

:::info
:::spoiler *Optimal Space & Time Complexity*
<br>

- Time complexity: O(n)
- Space complexity: O(n)

:::

<br>

## Thoughts & Solutions

### 朵
- go through string and check character is left bracket,then append in the stack_list.
- check character is right bracket,then
- character == ')' and pop stack value == '('
- character == '}' and pop stack value == '{'
- character == ']' and pop stack value == '['
- check stack_list whether it is empty.

:::spoiler Code

class Solution:
    def isValid(self, s: str) -> bool:
        ## method 1
        brackets=[]
        if not len(s)%2==0:
            return False
        for character in s:
            if character in ['(','{','[']:
                brackets.append(character)
            elif character in [')','}',']']:
                if not brackets:
                    return False
                right_bracket=brackets.pop()
                if not character ==')' and right_bracket =='(' or\
                    not character =='}' and  right_bracket =='{' or\
                    not character ==']' and right_bracket =='[' :
                    return False
            else:
                 pass
                 
        if brackets:
            return False
        else:
            return True

        ## method 2
        stack = []
        pairs = {
            '(': ')',
            '{': '}',
            '[': ']'
        }
        for bracket in s:
            if bracket in pairs:
                stack.append(bracket)
            elif len(stack) == 0 or bracket != pairs[stack.pop()]:
                return False

        return len(stack) == 0

:::

<hr/>

### 東

:::spoiler Code

const openCloseMap = {
    "(" : ")",
    "[" : "]",
    "{" : "}"
};

var isValid = function(s) {
    const stack = [];
    for(const ch of s) {
        if(ch in openCloseMap) {
            stack.push(ch);
        } else {
            if(ch !== openCloseMap[stack.pop()]) return false;
        }
    }
    return true;
}

:::

<hr/>

### Jessie

:::spoiler Code

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {

    const regex = /\[\]|\{\}|\(\)/g;

    //  Remove pair till can not do it anymore.
    while (s.length !== 0) {

        let oldLen = s.length;

        s = s.replaceAll(regex, '');
        
        if (s.length === 0) return true;
        if (s.length === oldLen) return false;

    }
};

:::

<hr/>

### YC
- push the open bracket into the stack
- pop the open bracket when it is closed
- check if the stack is empty
:::spoiler Code

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    const openBrackets = ['(', '{', '[']
    const pair = {
        ')':'(',
        '}':'{',
        ']':'['
    }

    const stack = [];
    for(const ch of s){
        // push the open bracket
        if(openBrackets.includes(ch)){
            stack.push(ch);
            continue;
        }

        // pop the open bracket
        if(pair[ch] === stack[stack.length - 1]){
            stack.pop();
            continue;
        }
        
        return false
    }

    return !stack.length;
};

:::

<hr/>

### Sol
:::spoiler Code

:::

<hr/>

<br/>

## Live Coding

:::spoiler (name)

// write your code here

:::