20-有效的括号

标签：栈字符串

题目信息

题目内容：

javascript

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

有效字符串需满足：
   左括号必须用相同类型的右括号闭合。
   左括号必须以正确的顺序闭合。
   每个右括号都有一个对应的相同类型的左括号。

示例 1：
  输入：s = "()"
  输出：true
  
示例 2：
  输入：s = "()[]{}"
  输出：true
  
示例 3：
  输入：s = "(]"
  输出：false

题解

解法一

思路：

这个题可以使用栈来解决
首先遍历字符串，遇到左括号就入栈，遇到右括号就判断栈顶是否与之匹配(因为规则中说明左括号必须以正确的顺序闭合，所以如果遇到右括号，此时栈顶的元素一定是该右括号对应的相同类型的左括号才匹配)
如果不匹配则返回false，匹配则出栈
遍历结束后，栈为空则返回true，否则返回false

代码实现：

javascript

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    const len = s.length
    // 如果字符串长度为奇数，直接返回false
    if(len % 2 !== 0) return false
    const stack = []
    const rightBrackets = [')', '}', ']']
    for(let i = 0; i < len; i++) {
        const curBracket = s[i]
        // 如果当前符号是左括号，就将其放到栈中
        if(!rightBrackets.includes(curBracket)) {
            stack.push(curBracket)
            continue
        }
        // 当前符号是右括号，但是栈中没有任何类型的左括号，直接返回false
        if(!stack.length) return false
        // 取栈顶的左括号，判断是否与当前右括号匹配
        const leftBracket = stack.pop()
        if(
            (curBracket === ')' && leftBracket !== '(') ||
            (curBracket === '}' && leftBracket != '{') ||
            (curBracket === ']' && leftBracket != '[')
        ) return false
    }
    // 如果循环完了栈中还有左括号，返回false
    return !stack.length;
};

rightBrackets也可以使用Map来代替，实现起来也更简单了，如下所示：

javascript

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    const len = s.length
    // 如果字符串长度为奇数，直接返回false
    if(len % 2 !== 0) return false
    const stack = []
    const rightBrackets = new Map([
        [')', '('],
        ['}', '{'],
        [']', '[']
    ])
    for(let i = 0; i < len; i++) {
        const curBracket = s[i]
        // 如果当前符号是左括号，就将其放到栈中
        if(!rightBrackets.has(curBracket)) {
            stack.push(curBracket)
            continue
        }
        // 当前符号是右括号，但是栈中没有任何类型的左括号，直接返回false
        if(!stack.length) return false
        // 取栈顶的左括号，判断是否与当前右括号匹配
        const leftBracket = stack.pop()
        if (leftBracket !== rightBrackets.get(curBracket)) return false
    }
    // 如果循环完了栈中还有左括号，返回false
    return !stack.length;
};

20-有效的括号 #

题目信息 #

题解 #

解法一 #

20-有效的括号

题目信息

题解

解法一