图解腾讯&哔哩哔哩&leetcode20：有效的括号

[sisterAn]

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

有效字符串需满足：

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

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

附赠leetcode：leetcode

[7777sea]

const answer = (s) => {
        const map = {
            '(': ')',
            '{': '}',
            '[': ']'
        }
        let _ = [];
        for(var i of s){
            if(map[i]){_.push(i)}
            else {
                if(i != map[_.pop()]) return false;
            }
        }
        return !_.length
    }``

[fanefanes]

方法： 检测这个字符串，是否符合一个完整出入栈流程， '(','{','[' 这类字符串为入栈 stack.push(),
')','}',']' 这类字符串为出栈 stack.pop(), 当执行结束stack.length = 0 时，return true 时间复杂度O(n), 空间复杂度O(n) 代码就是楼上的for 循环解释

[13001920223]

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

  const brackets = []
  
  if (s % 2) return false

  for (const i of s) {
    switch(i) {
      case '{':
        brackets.push(i)
        break
      case '[':
        brackets.push(i)
        break
      case '(':
        brackets.push(i)
        break
      case '}':
        if (brackets.pop() !== '{') return false
        break
      case ']':
        if (brackets.pop() !== '[') return false
        break
      case ')':
        if (brackets.pop() !== '(') return false
        break
    }
  }
  return brackets.length === 0
};

[sisterAn]

解答：利用栈结构

解题思路： 将字符串中的字符依次入栈，遍历字符依次判断：

• 首先判断该元素是否是 { 、 ( 、 [ ，直接入栈
• 否则该字符为 } 、 ) 、 ] 中的一种，如果该字符串有效，则该元素应该与栈顶匹配，例如栈中元素有 ({， 如果继续遍历到的元素为 ), 那么当前元素序列为 ({) 是不可能有效的，所以此时与栈顶元素匹配失败，则直接返回 false ，字符串无效

当遍历完成时，所有已匹配的字符都已匹配出栈，如果此时栈为空，则字符串有效，如果栈不为空，说明字符串中还有未匹配的字符，字符串无效

画图帮助理解一下：

代码实现：

const isValid = function(s) {
    let map = {
        '{': '}',
        '(': ')',
        '[': ']'
    }
    let stack = []
    for(let i = 0; i < s.length ; i++) {
        if(map[s[i]]) {
            stack.push(s[i])
        } else if(s[i] !== map[stack.pop()]){
            return false
        }
    }
    return stack.length === 0
};

时间复杂度：O(n)

空间复杂度：O(n)

leetcode

[zero9527]

/**
 * 有效的括号
 * 
 * 要求：
  给定一个只包括 '(' ，')' ，'{' ，'}' ，'[' ，']' 的字符串，判断字符串是否有效。

  有效字符串需满足：
    左括号必须用相同类型的右括号闭合。
    左括号必须以正确的顺序闭合。
    注意空字符串可被认为是有效字符串。
 */

function validBrackets(str) {
  if (typeof str !== 'string') return false;
  if (str === '') return true;

  const matches = ['()', '[]', '{}'];
  const leftStr = replaceMatch(str);

  // 匹配并替换，直到不能匹配
  function replaceMatch(str) {
    const matchItem = matches.find((i) => str.includes(i));
    if (matchItem) {
      str = str.replace(matchItem, '');
      if (str.length) str = replaceMatch(str);
    }
    return str;
  }

  if (leftStr.length !== 0) console.log('leftStr: ', leftStr);

  // 匹配完 leftStr === '' 则是括号正确
  return leftStr.length === 0;
}

const v = validBrackets;
console.log('(): ', v('()')); // true
console.log('()[]{}: ', v('()[]{}')); // true
console.log('(]: ', v('(]')); // false
console.log('([)]: ', v('([)]')); // false
console.log('{[]}: ', v('{[]}')); // true
console.log('{[}](): ', v('{[}]()')); // false
console.log('(){[}][]: ', v('(){[}][]')); // false
console.log(')(][: ', v(')(][')); // false
console.log('{[({[]})]}: ', v('{[({[]})]}')); // false
console.log('{[({[()]})]: ', v('{[({[()]})]')); // false
console.log('haha: ', v('haha')); // false

[qianlongo]

var isValid = function(s) {
  const charMap = {
    '(': ')',
    '[': ']',
    '{': '}',
  }
  const charStack = []
  
  for (let i = 0, len = s.length; i < len; i++) {
    const char = s.charAt(i)
    const hitChar = charMap[ char ]

    if (hitChar) {
      charStack.push(hitChar)
    } else if (charStack.pop() !== char) {
      return false
    }
  }

  return charStack.length === 0
};

[yucheng-yc]

作了套面试题，我的解法如下

题目： 第一题（20分）：给定一个字符串，里边可能包含“()”、"{}"、“[]”三种括号，请使用JavaScript实现一个函数 function testFn(str){...}， 检查该字符串的括号是否成对出现。 例如： “(a[b(c)d]e{f}g)” //true “(a[b(cd]e{f}g))” //false “(a[b(c)d]e{f}” //false 解法： function testFn(str){ if(!str.length) { return true } let resStr = str.replace(/[^{}[]()]/ig,"") if(resStr.length%2===0) { const length = resStr.length for(let i = 0;i<length/2;i++) { resStr= resStr.replace(/([])|(())|({})/ig,"") console.log('resStr',i, resStr) } return !resStr

}else {
    return false
}

} console.log(testFn('(a[b(c)d]e{f}g)')) console.log(testFn('(a[b(cd]e{f}g))')) console.log(testFn('(a[b(c)d]e{f}'))

[AnranS]

var isValid = function (s) {
    let map = new Map();
    map.set('}', '{');
    map.set(')', '(');
    map.set(']', '[');

    let right = ['}', ')', ']'];
    let tmpStack = new Array();

    for (let i = 0; i < s.length; i++) {
        if(right.indexOf(s[i]) === -1){
            tmpStack.push(s[i]);
        } else {
            let tmp = tmpStack.pop();
            if(tmp !== map.get(s[i])) return false;
        }
    }
    return tmpStack.length === 0;
};

[z253573760]

function isValid(str) {
  const map = {
    "{": "}",
    "[": "]",
    "(": ")",
  };
  const stack = [];
  for (const item of str) {
    const last = stack[stack.length - 1];
    if (map[last] === item) {
      stack.pop();
    } else {
      stack.push(item);
    }
  }
  console.log(stack.length === 0);
  return stack.length === 0;
}
isValid("()"); //true
isValid("()[]{}"); //true
isValid("(]"); //false
isValid("{[]}"); //true

[JohnApache]

利用栈保存读取到的字符，判断是否为有效，只需判断当出现反向符号的时候，栈顶符号一定是对应的正向符号，如果是，就推出栈顶符号，继续遍历，如果不是直接返回false，

const isValid = (source: string) => {
    const len = source.length;
    if (len <= 0) return false;
    const CharMap: Record<string, string> = {
        ')': '(',
        '}': '{',
        ']': '[',
    };
    const stack: string[] = [ source[0] ];
    for (let i = 1; i < len; i++) {
        const char = source[i];
        if (!CharMap[char]) {
            stack.push(char);
            continue;
        }

        // 出现反向符号，且反向符号对应的正向符号 !== 栈顶的符号，肯定不符合规则直接返回false
        if (CharMap[char] !== stack[stack.length - 1]) return false;
        stack.pop();
    }
    return stack.length <= 0;
};

[self-transition]

var isValid = function(s) {
    s= s.split('')
    let map = new Map([['(', ')'], ['{', '}'], ['[', ']']])
    let stack = []
    for (let i=0;i<s.length;i++) {
        if (map.get(s[i])) {
            stack.push(s[i])
        } else {  
            if (s[i] !== map.get(stack.pop())) return false
        }
    }
    return !stack.length
};

[AlexZhang11]

let mapBrackets = {
    "(":")",
    "[":"]",
    "{":"}",
}
function validBrackets(str){
    let stack = []
    for(let i = 0;i<str.length;i++){
        let c = str.charAt(i)
        if(['(','{','['].includes(c)){
            stack.push(mapBrackets[c])
        }else if(!stack.length||stack.pop()!=c){
            return false
        }
    }
    return !stack.length
}

console.log(validBrackets("()"))
console.log(validBrackets("()[]{}"))
console.log(validBrackets("(]"))
console.log(validBrackets("([)]"))
console.log(validBrackets("{[]}"))