Java教程

有效的括号

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

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匹配括号代码会简洁很多
这篇关于有效的括号的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!