20. Valid Parentheses.md

​

20. Valid Parentheses

Easy

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

Given a string 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.

Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

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

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

解题：

1. 使用栈
2. 遇到左括号，直接 push 到数组
3. 如果遇到右括号，则分析不同场景
   1. 如果栈不为空且当前和左边的值组成正确的闭合，则取出栈顶元素pop,继续循环
   2. 如果栈为空，则直接返回 false
   3. 若不能和左边的值形成闭合，则返回false

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    let valid = true;
    const mapper = {
        '{': "}",
        "[": "]",
        "(": ")"
    }
    const stack = [];    
    for (let i in s) {
        const c = s[i];
        if(['(', '[', '{'].indexOf(c) > -1) {
            stack.push(c)
        } else {
            const peak = stack.pop();
            if(c !== mapper[peak]) {
                return false
            }
        }
    }
    
    if (stack.length > 0) {
        return false;
    } 
    return valid;
};