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

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

有效字符串需满足：

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

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

示例 1:

输入: "()"
输出: true

示例 2:

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

示例 3:

输入: "(]"
输出: false

示例 4:

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

示例 5:

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

附赠leetcode：leetcode

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
    }``

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

/**
 * @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
};

解答：利用栈结构

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

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

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

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

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

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
};

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

题目：
第一题（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}'))

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;
};

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

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

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
};

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("{[]}"))

Navigation Menu

Repository navigation

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

解答：利用栈结构

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

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

Description

Activity

7777sea commented on Apr 23, 2020

fanefanes commented on Apr 23, 2020

13001920223 commented on Apr 23, 2020

sisterAn commented on Apr 23, 2020

解答：利用栈结构

zero9527 commented on Apr 30, 2020

qianlongo commented on Aug 22, 2020

yucheng-yc commented on Nov 18, 2020

AnranS commented on Nov 18, 2020

z253573760 commented on Feb 3, 2021

JohnApache commented on Apr 29, 2021

self-transition commented on May 13, 2022

AlexZhang11 commented on May 31, 2024

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions