有效的括号

本文主要是介绍有效的括号，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

leetcode传送门
题目大意
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

• 用数组实现stack，top标识栈顶指针
• 遍历字符串s，遇到左括号就压栈；遇到右括号和栈顶元素比较，两者匹配的话，栈顶元素出栈。
• 通过栈是否为空来判断是否为有效括号

解法一：
不适用Map匹配括号

/**
 * @param {string} s
 * @return {boolean}
 */
 var isValid = function(s) {
    let stack = [];
    let top = -1;//栈顶指针
    //遍历字符串
    for( let i = 0; i < s.length; i ++) {
        if(s[i] === '(' || s[i] === '[' || s[i] === '{') {
            top ++;
            stack.push(s[i]);//压栈
        } else if(s[i] === ')' && stack[top] === '(' 
        || s[i] === ']' && stack[top] === '['
        || s[i] === '}' && stack[top] === '{') {
            stack.pop();//出栈
            top --;
        } else 
            return false;//防止右括号在左括号左边等
    }
    //通过栈是否为空来判断括号是否有效
    if( top === -1 )
        return true;
    else    
        return false;
};

解法二：
使用Map匹配括号

/**
 * @param {string} s
 * @return {boolean}
 */
 var isValid = function(s) {
    let stack = [];
    let top = -1;//栈顶指针
    let map = new Map();
    map.set("(",")");
    msp.set("[","]");
    map.set("{","}");
    for (let i = 0; i < s.length; i ++) {
        if(stack.length > s.length / 2) 
            return false;
        if(map.has(s[i])) {
            top ++;
            stack.push(s[i]);
        } else if(s[i] === map.get(stack[top])) {
            stack.pop();
            top --;
        } else 
            return false;
    }
    //通过栈是否为空来判断括号是否有效
    if( top === -1 )
        return true;
    else    
        return false;
};

说点什么

• 使用Map匹配括号代码会简洁很多

这篇关于有效的括号的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！