讨论/技术交流/算法题【有效的括号】求助/
算法题【有效的括号】求助

leetcode算法题有效括号 20. 有效的括号,括号必须是按这样的顺序排列 {}、[]、(),具体的我也记不清了,求大佬们解答。最好用javascript。

共 5 个回复

在一次字节笔试中做过这个题,貌似是{ ( [ 有不同的优先级??

哦,应该也是大同小异的,像括号这类问题基本上就是栈

不是的大佬,我想问的不是这道题,是这道题的延申题,leetcode上没有,我是在字节跳动笔试遇到的,忘记截图了具体什么规则我也记不清了,就是它的括号是有顺序的{[()]},类似这样,就是想看看大佬们有没有见过这道题。谢谢啦大佬!

容我先说一句,你以后还是不要直接放讨论里面等人发代码了,自己可以去看题解。
不在LC上的题再来发。
这道题其实很简单,一个栈就行。
本人只会Python,JS是xiao_ben_zhu写的。

const isValid = (s) => {
  const stack = [];

  for (let i = 0; i < s.length; i++) {
    const c = s[i];
    if (c == '{' || c == '[' || c == '(') { // 是左括号,入栈
      stack.push(c);
    } else {                                // 是右括号
      if (stack.length == 0) {              // 此时栈空,无法匹配
        return false;
      }
      const top = stack[stack.length - 1];  // 获取栈顶
      if (top == '(' && c == ')' || top == '[' && c == ']' || top == '{' && c == '}') {
        stack.pop();                        // 如果栈顶是对应的左括号,被匹配,出栈
      } else {                              // 不是对应的左括号,无法匹配
        return false;
      }
    }
  }
  return stack.length == 0; // 栈空,则所有左括号找到匹配;栈中还剩有左括号,则没被匹配
};
class Solution:
    def isValid(self, s: str) -> bool:
        a = []
        b = {")":"(" , "]":"[" , "}":"{"}
        for i in range(len(s)):
            if s[i] in ["(","[","{"]:
                a.append(s[i])
            if s[i] in [")","]","}"]:
                if len(a) == 0 or b[s[i]] != a[len(a)-1]:
                    return False
                else:
                    del a[len(a)-1]
        if len(a) != 0:
            return False
        return True
var isValid = function(s) {
    const stack = [];
    for (let i = 0; i < s.length; i ++) {
        switch(s[i]) {
            case '(' : stack.push(1);break;
            case '[' : stack.push(2);break;
            case '{' : stack.push(3);break;
            case ')' : if (stack.pop() !==1 ) return false;break;
            case ']' : if (stack.pop() !==2 ) return false;break;
            case '}' : if (stack.pop() !==3 ) return false;break;
        }
    }
    return !stack.length;
};