Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Valid Parentheses

Leetcode algorithms 第 20 题:Valid Parentheses。

题目

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[' and ']‘, determine if the input string is valid.

The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.

解答

括号匹配问题。使用栈解决,遍历字符串,遇到左括号入栈,遇到右括号,则

  • 如果栈顶为对应的左括号,则栈顶元素出栈,继续遍历。
  • 否则,括号不匹配,返回false。

最后栈为空则返回true。这里判断括号是否匹配可以简单地使用+1进行,因为右括号比对应的左括号大1。

具体代码如下:

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for (int i = 0; i < s.length(); i++)
            if (s[i]=='(' || s[i]=='[' || s[i]=='{')//左括号入栈
                st.push(s[i]);
            else if (!st.empty() && (st.top()==s[i]-1 || st.top()==s[i]-2))
                st.pop();   //ASCII关系:)=(+1,]=[+2, }={+2
            else
                return false;
        return st.empty();
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论