LeetCode算法--判断括号是否有效

题目：给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。

解析：因为括号是成对出现的，所以，我们首先可以判断一下长度，如果是奇数，那么直接返回false。其次，我们很容易就可以想到栈的思想，因为栈的特点是先进后出。所以，我们可以栈的近出，来比对是否是有效字符串。

//  通过字典来存储括号对
const dic = {'}': '{', ')': '(', ']': '['}
var isValid = function(s) {
    //  判断字符串是不是奇数
    if (!s || s.length % 2 !==0) return false
    let stack = []
    for (let key of s) {
        //  如果是向右侧的括号押入栈中
        if (key === '{' || key === '(' || key === '[') {
            stack.push(key)
        } else {
            //  如果栈为空，说明括号对缺乏向右侧的半边，返回false
            //  依次出栈与入栈不同，那么就返回false
            if (!stack.length || stack.pop() !== dic[key]) {
                return false
            }
        }
    }
    //  最终如果栈为空，那么字符串是有效的返回true
    return !stack.length
}
isValid('[()]{}')   //  true

注：利用不同数据结构，本题中主要是利用栈结构的原理，相对比较简单。