LC-20 有效的括号

Easy

给定一个只包括 ‘(‘,’)’,'{‘,’}’,'[‘,’]’ 的字符串,判断字符串是否有效。

有效字符串需满足:

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 注意空字符串可被认为是有效字符串。

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


解:使用栈作为中间数据结构

  1. 初始化栈 S。
  2. 从左到右依次处理表达式的每个括号。
  3. 如遇到开括号,将其推到栈上即可。
  4. 遇到闭括号,那么检查栈顶的元素。如果栈顶的元素是一个 相同类型的 左括号,那么我们将它从栈中弹出并继续处理。否则,这意味着表达式无效。
  5. 如果到最后我们剩下的栈中仍然有元素,那么这意味着表达式无效。
  • 时间复杂度O(n)
  • 空间复杂度O(n)
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    if (s === '') return true
    let stack = new Array()
    let ans = true
    for(let i = 0; i < s.length; i++) {
        if (s[i] === '{' || s[i] === '[' || s[i] === "(") {
            stack.unshift(s[i])
        } else {
            if (stack[0] === '{' && s[i] === '}') stack.shift()
            else if (stack[0] === '[' && s[i] === ']') stack.shift()
            else if (stack[0] === '(' && s[i] === ')') stack.shift()
            else ans = false
        }
    }
    return stack.length === 0 && ans
};

// 栈先入后出。后进的左括号最先删除,最后判断栈的长度和某些特殊情况(如只有一个右括号的情况)