Leetcode第二十题(有效的括号)

简介: 这篇文章介绍了如何使用栈来解决LeetCode第20题“有效的括号”问题,提供了两种方法:数组栈和容器栈,以及相应的C++代码实现。

题目描述:

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

有效字符串需满足:

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

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

示例 3: 输入:s = "(]" 输出:false
示例 4: 输入:s = "([)]" 输出:false
示例 5: 输入:s = "{[]}" 输出:true

无论是用数组栈,还是容器栈去解决括号匹配的问题,首先,遵循括号匹配的字符串任何一个前缀,其左括号的个数一定是大于等于右括号的个数的。其思路都是先用hash表存储所有类型的括号,左括号为key,右括号为value,遍历括号字符串,如果当前字符为左括号,那么入栈该左括号对应的右括;如果为右括号,将该右括号与栈顶字符比较, 如果不相等或者此时栈为空, 那么肯定括号不匹配,直接返回false。反之相等就出栈该右括号, 如果遍历完字符串后, 栈为空, 那么说明括号是左右相匹配的, 返回true

数组栈:

class Solution {
public:
    bool isValid(string s) {
        unordered_map<char,char> pairs = {
            {'(',')'},{'{','}'},{'[',']'}
        };
        char stck[4096];
        int top = -1;
        for(int i = 0;i < s.length();i++){
            if(pairs.find(s[i]) != pairs.end()){  //当前为左括号,入栈右括号
                stck[++top] = pairs[s[i]];
            }else{
                if(top == -1 || stck[top] != s[i]) //当前为右括号不等于栈顶括号,或者栈空
                    return false;
                else                               //当前为右括号等于栈顶括号,出栈
                    stck[top--];
            }
        }
        return top == -1;                         //栈为空返回true
    }
};

容器栈:

class Solution {
public:
    bool isValid(string s) {
        unordered_map<char,char> pairs = {
            {'(',')'},{'{','}'},{'[',']'}
        };
        stack<char> st;
        for(int i = 0;i < s.length();i++){
            if(pairs.find(s[i]) != pairs.end()){  //当前为左括号,入栈右括号
                st.push(pairs[s[i]]);
            }else{
                if(st.empty() || st.top() != s[i]) //当前为右括号不等于栈顶括号,或者栈空
                    return false;
                else                               //当前为右括号等于栈顶括号,出栈
                    st.pop();
            }
        }
        return st.empty();                         //栈为空返回true
    }
};
相关文章
|
6月前
|
存储 C语言 索引
环形链表、环形链表 II、有效的括号​​​​​​​【LeetCode刷题日志】
环形链表、环形链表 II、有效的括号​​​​​​​【LeetCode刷题日志】
|
2天前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
1月前
|
算法 C++
Leetcode第二十二题(括号生成)
这篇文章讨论了如何使用递归算法解决LeetCode第22题“括号生成”的问题,提供了两种C++的实现方法,目的是生成所有有效的括号组合。
13 0
Leetcode第二十二题(括号生成)
|
3月前
|
算法
LeetCode第22题括号生成
该文章介绍了 LeetCode 第 22 题括号生成的解法,通过回溯算法生成所有可能的括号组合,在递归过程中根据左右括号数量的条件进行剪枝,从而得到有效的括号组合。
LeetCode第22题括号生成
|
3月前
|
存储 算法
LeetCode第20题有效的括号
该文章介绍了 LeetCode 第 20 题有效的括号的解法,通过分析有效括号的特征,使用栈结构存储括号关系,判断遇到右边括号时栈顶是否有匹配的左边括号,从而解决问题,同时总结了栈的先进后出结构可用于解决有规律的符号匹配问题。
LeetCode第20题有效的括号
|
3月前
|
算法 Python
【Leetcode刷题Python】括号匹配问题
一种解决括号匹配问题的Python实现方法,通过计算给定括号串的所有子串的最长合法括号子序列长度之和来确定权值。
23 0
|
3月前
|
机器学习/深度学习 Python
【Leetcode刷题Python】22. 括号生成
本文介绍了了LeetCode题目22的两种Python编程解决方案,题目要求生成所有可能的且有效的括号组合,包括暴力求解和回溯方法。
23 0
|
3月前
|
Python
【Leetcode刷题Python】20. 有效的括号
LeetCode上题目“20. 有效的括号”的Python解决方案,使用栈数据结构来验证括号序列的有效性。具体实现中,会在栈中预先放置一个特殊字符以避免在弹出操作时出现空栈错误,并通过匹配左右括号来判断括号序列是否有效。
41 0
|
5月前
|
算法 Java C语言
【经典算法】LeetCode 20:有效的括号(Java/C/Python3实现含注释说明,Easy)
【经典算法】LeetCode 20:有效的括号(Java/C/Python3实现含注释说明,Easy)
40 1
|
4月前
|
算法 测试技术
力扣经典150题第五十一题:有效的括号
力扣经典150题第五十一题:有效的括号
37 0