当前位置：网站首页>LeetCode 20、有效的括号

LeetCode 20、有效的括号

2022-04-23 20:23:00 【亡于灬】

20、有效的括号

1）题目描述

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

有效字符串需满足：

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

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

示例 4：

输入：s = "([)]"
输出：false

示例 5：

输入：s = "{[]}"
输出：true

提示：

  • 1 <= s.length <= 10^4
  • s 仅由括号 '()[]{}' 组成

2）分析

利用栈的先入后出特性，使用栈来解决。

  • 括号完成配对，那么字符串一定是偶数长度；
  • 遍历字符串，若是左括号，则向栈中压入相应的右括号；
  • 若是右括号，判断栈顶字符是否与其相等，若不相等，返回false；
  • 遍历结束，若栈为空，返回true，否则返回false。

3）C++代码

class Solution {
    
public:
    bool isValid(string s) {
    
        if(s.length()%2)
            return false;
        stack<int> stk;
        for(int i=0;i<s.length();i++){
    
            if(s[i]=='(')
                stk.push(')');
            else if(s[i]=='[')
                stk.push(']');
            else if(s[i]=='{')
                stk.push('}');
            else if(stk.empty()||stk.top()!=s[i])
                return false;
            else
                stk.pop();
        }
        return stk.empty();
    }
};

版权声明
本文为[亡于灬]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qq_38342510/article/details/124360469

边栏推荐

猜你喜欢

随机推荐