图解腾讯&哔哩哔哩&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