AcWing
  • 首页
  • 题库
  • 题解
    • LeetCode
    • AcWing
  • 分享
  • 问答
  • 活动
  • 应用
  • 吐槽
  • 登录/注册

LeetCode 20. Valid Parentheses    原题链接    简单

作者: 作者的头像   wzc1995 ,  2018-03-28 16:05:19 ,  阅读 951


3


1

题目描述

给定一个嵌套的括号序列,含有 ( ) [ ] { } 三种括号,判断序列是否合法。

样例

"()" 和 "()[]{}" 是合法的;
"(]" 和 "([)]" 不是合法的。

算法

(栈结构) $O(n)$

使用栈数据结构:

  1. 遇到左括号,需要压栈。
  2. 遇到右括号,判断栈顶是否和当前右括号匹配;若不匹配则返回false,否则匹配弹出栈顶。
  3. 最后判断栈是否为空;若为空则合法,否则不合法。

时间复杂度

  • 只需要遍历一次整个序列,所以是 $O(n)$ 的。

空间复杂度

  • 栈需要 $O(n)$ 的空间。

C++ 代码

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

评论列表:


用户头像
小雨   2018-11-11 20:24     回复

the best way to think about how to solve a question is to think about both positive cases and the negative cases, I used to focus on the positive cases, but I realized that it’s more helpful to look at things from the other side. Some thoughts about this question. ^_^

你确定删除吗?

© 2018-2019 AcWing 版权所有  |  京ICP备17053197号-1
联系我们  |  常见问题
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息