当前位置:首页 > 力扣 > 用栈结构优雅破解括号匹配难题(力扣20题)

用栈结构优雅破解括号匹配难题(力扣20题)

2个月前 (05-15)

用栈结构优雅破解括号匹配难题(力扣20题) 字符串 栈 数据结构 力扣 算法 C++ 迭代 第1张

一、题目重新解读

给定一个仅包含 ('、')、'['、']'、'{'、'}' 的字符串,判断其是否有效。有效需满足:

1. 左括号必须与相同类型的右括号闭合(如 () 对应,[] 对应,{} 对应);

2. 闭合顺序必须正确(先开的括号后闭);

3. 不存在未匹配的括号。



二、解题思路与过程

1. 栈结构特性:“后进先出(LIFO)”的特性天然适配括号匹配——后出现的左括号需先被匹配。

2. 遍历策略:

    1.遇左括号直接压栈,记录“待匹配项”;

    2.遇右括号时:

    3.若栈空,说明右括号无对应左括号(如 ])),直接返回假;

    4.若栈顶左括号与当前右括号不匹配(如 ][),返回假;

    5.匹配成功则弹栈,继续下一字符。

3. 最终判断:遍历结束后,栈为空说明所有括号均匹配,否则存在剩余左括号(如 (])。


三、代码与注释

class Solution {
public:
    // 判断字符是否为左括号的优雅舞步
    bool IsLift(char a) {
        return a == '(' || a == '[' || a == '{'; // 简洁的三重判断
    }

    bool isValid(string s) {
        if(s.size()&1) return false; // 奇数长度直接谢幕

        stack<char> s1; // 创建记忆栈
        for(int i=0; i<s.size(); i++) {
            if(IsLift(s[i])) {
                s1.push(s[i]); // 收集未完成的期待
            } else {
                if(s1.empty()) return false; // 空栈遇右括号必定失格
                
                // 检查栈顶元素是否与当前右括号共鸣
                if( (s1.top()=='(' && s[i]==')') || 
                    (s1.top()=='[' && s[i]==']') ||
                    (s1.top()=='{' && s[i]=='}') ) {
                    s1.pop(); // 成功配对则释放栈顶
                } else {
                    return false; // 不和谐音出现
                }
            }
        }
        return s1.empty(); // 最终校验所有期待都已满足
    }
};


原创内容 转载请注明出处

分享给朋友:

相关文章

手把手教你实现头插法树:从代码到原理的深度解析

一、简介和特点头插法树是一种基于链表实现的树形数据结构,其核心思想是通过链表头插法管理节点的孩子节点。在本文的代码示例中,我们使用C++模板类实现了树结构,每个树节点(treenode<T>...

力扣第44题:寻找两个正序数组的中位数 - 合并排序解法详解

力扣第44题:寻找两个正序数组的中位数 - 合并排序解法详解

内容简介本文详细解析了力扣第44题"寻找两个正序数组的中位数"的合并排序解法。通过双指针技术合并两个有序数组,然后直接计算合并后数组的中位数。虽然时间复杂度为O(m+n),但这种方...

手搓二叉搜索树代码详解:从入门到实现(附完整注释)

一、简介和应用二叉搜索树(Binary Search Tree,BST)是一种经典的数据结构,其特点在于每个节点的左子树所有节点值均小于该节点,右子树所有节点值均大于该节点。这种特性使得它在查找、插入...

标题:洛谷B3617题解析:八进制转十六进制算法实现与优化(附AC100代码)

标题:洛谷B3617题解析:八进制转十六进制算法实现与优化(附AC100代码)

一、题目解读洛谷B3617题要求将输入的八进制字符串转换为十六进制表示。题目需处理大数场景,且对输入合法性有明确限制(长度不超过1000,仅包含0-7字符)。由于八进制与十六进制无法直接转换,需借助十...

力扣3112题解法:带时间限制的最短路径问题解析(C++代码)

力扣3112题解法:带时间限制的最短路径问题解析(C++代码)

一、题目解读力扣3112题要求解决带时间限制的最短路径问题:给定一个有向图,节点具有消失时间,需计算从起点到各节点的最短路径,且路径总时间不能超过节点的消失时间。题目难点在于需在传统最短路径算法(如D...

【洛谷1184题解析】用C++高效解决地点匹配问题(附代码与解题思路)

【洛谷1184题解析】用C++高效解决地点匹配问题(附代码与解题思路)

一、题目解读洛谷1184题要求处理一组地点列表与行程记录,统计其中匹配的天数。题目难点在于高效处理带有空格的字符串输入,以及快速判断每日行程是否在高手可去地点集合中。需要兼顾输入格式解析与算法效率。二...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。