有效的括号

Tips

题目类型: Stack

题目

给定一个只包括 (, ), {, }, [, ] 的字符串 s, 判断字符串是否有效. 有效字符串需满足:

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

提示:

• 1 <= s.length <= 10⁴
• s 仅由括号 '()[]{}' 组成

示例

输入: s = '()[]{}'
输出: true

输入: s = '(]'
输出: false

题解

遇见括号问题先想到栈. 遍历字符串, 如果遇到 (, {, [, 压入栈中; 如果遇到 ), }, ], 看看栈顶能不能找到对应的左括号, 如果找到, 就弹出栈顶元素, 否则就匹配不上了. 最终如果是有效的括号, 栈在遍历完后应该是空的.

JavaScript

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

  // 如果是奇数, 一定不是合法的括号
  if (n % 2 === 1) return false

  const stack = []

  for (const ch of s) {
    if (ch === '{' || ch === '[' || ch === '(') {
      stack.push(ch)
    } else {
      const top = stack[stack.length - 1]

      if (top === '{' && ch === '}') stack.pop()
      else if (top === '[' && ch === ']') stack.pop()
      else if (top === '(' && ch === ')') stack.pop()
      else return false
    }
  }

  return stack.length === 0
}

Rust

pub fn is_valid(s: String) -> bool {
    let mut stack = vec![];

    for ch in s.chars() {
        match ch {
            '(' | '[' | '{' => stack.push(ch),
            ')' => {
                if stack.pop() != Some('(') {
                    return false;
                }
            }
            ']' => {
                if stack.pop() != Some('[') {
                    return false;
                }
            }
            '}' => {
                if stack.pop() != Some('{') {
                    return false;
                }
            }
            _ => return false,
        }
    }

    stack.is_empty()
}