跳至主要內容

有效的括号

linwu大约 2 分钟

有效的括号

给定一个只包含字符'('')''{''}''['']'的字符串str,判断该字符串中的括号是否有效。

为了判断括号是否有效,需满足以下条件:

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

注意空字符串也被视为有效。

示例:

输入:str = "()" 输出:true 解释:括号字符串"()"是有效的。

输入:str = "()[]{}" 输出:true 解释:括号字符串"()[]{}"是有效的。

输入:str = "(]" 输出:false 解释:括号字符串"(]"是无效的,左括号必须用相同类型的右括号闭合。

输入:str = "([)]" 输出:false 解释:括号字符串"([)]"是无效的,左括号必须以正确的顺序闭合。

题目分析与解题步骤:

这个问题可以使用栈来解决。我们可以遍历字符串中的每个字符,并使用一个栈来模拟括号的匹配过程。对于每个字符,我们根据其类型进行操作。

解题步骤如下:

  1. 创建一个栈stack,用于模拟括号的匹配过程。

  2. 遍历字符串str中的每个字符,并执行以下操作:

    • 如果当前字符是左括号({[,则将其入栈。

    • 如果当前字符是右括号)}],则需要进行匹配操作。

      • 如果栈为空,或栈顶元素与当前字符不匹配,则返回false,表示括号无效。

      • 如果栈顶元素与当前字符匹配,将栈顶元素出栈,继续遍历下一个字符。

  3. 遍历完整个字符串后,如果栈为空,则表示括号有效,返回true;否则,表示括号无效,返回false

JavaScript解题框架:

function isValid(str) {
  let stack = new Stack();

  for (let char of str) {
    if (char === '(' || char === '{' || char === '[') {
      stack.push(char);
    } else if (char === ')' || char === '}' || char === ']') {
      if (stack.isEmpty() || !isMatching(stack.pop(), char)) {
        return false;
      }
    }
  }

  return stack.isEmpty();
}

function isMatching(left, right) {
  return (
    (left === '(' && right === ')') ||
    (left === '{' && right === '}') ||
    (left === '[' && right === ']')
  );
}

在这个框架中,我们首先定义了一个栈类Stack,其中包含了常用的栈操作方法。然后,我们使用栈来判断括号是否有效。

isValid函数中,我们遍历字符串str,并根据字符的类型进行判断和操作。如果当前字符是左括号,将其入栈;如果当前字符是右括号,则进行匹配操作。

匹配操作通过isMatching函数来判断栈顶元素与当前字符是否匹配。如果栈为空,或栈顶元素与当前字符不匹配,则返回false,表示括号无效。

最后,判断栈是否为空,如果为空,则表示括号有效,返回true;否则,表示括号无效,返回false

关注公众号

和小伙伴们一起学习

加入技术交流群

扫描二维码 备注加群