欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode 20. 有效的括号(Valid Parentheses)

程序员文章站 2022-05-20 13:19:02
...

栈思想

关于有效括号表达式的一个有趣属性是有效表达式的子表达式也应该是有效表达式。

整个表达式是有效的,而它的子表达式本身也是有效的。这为问题提供了一种递归结构。(栈思想)

从整体表达式中一次删除一个较小的表达式,因为这是一个有效的表达式,我们最后剩留下一个空字符串。

class Solution {
public:
    bool isValid(string s) {
        int pos = 0;
        while (pos < s.length()){
            //左括号,压栈
            if (s[pos] == '(' || s[pos] == '{' || s[pos] == '[') {
                pos++;
                continue;
            }
            //括号匹配,出栈
            if((s[pos] == ')' && s[pos-1] == '(') || (s[pos] == ']' && s[pos-1] == '[') || (s[pos] == '}' && s[pos-1] == '{'))
            {
                s.erase(pos-1, 2);
                pos--;
            }
            else
                return false;
        }
        if (s.length() == 0)
            return true;
        else 
            return false;
    }
};

 

相关标签: