20. Valid Parentheses

Leetcode

https://leetcode.com/problems/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.

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Example 4:

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

Example 5:

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

分析

感覺這一題的描述不太完整，不能確定哪種排列算是 valid 的

解答

• 方法一 - Stack

用後進先出的 Stack 來存放 open 的括號，然後在遍歷的過程中，如果遇到 close 的括號就跟 Stack 最上層 open 的括號比對看是不是可以配對成同一組，那如果遇到的是 open 的括號就再把他加入到 Stack 裡

var isValid = function(s) {
    const stack = [s[0]];
    const mapEndToStartBracket = {
        ")": "(",
        "}": "{",
        "]": "["
    }
    
    for(let i=1; i<s.length; i++) {
        const char = s[i];
        const start = mapEndToStartBracket[char];
        // char 是 ) or } or ]
        if(start) {
            if(stack.pop() !== start) return false;
        } else {
            stack.push(char);
        }
    }
    
    return !stack.length;
};

Runtime: 76 ms, faster than 68.47% of JavaScript online submissions for Valid Parentheses.

Memory Usage: 38.9 MB, less than 74.18% of JavaScript online submissions for Valid Parentheses.

測資

let s = "()[]{}"; // true
s = "([)]"; // false
s = "{[]}"; // true

console.log(isValid(s))