Valid Parentheses - LeetCode

目录

题目链接

Valid Parentheses - LeetCode

注意点

  • 考虑输入为空的情况

解法

解法一:如果是'('、'{'、'['这三者就入栈,否则就判断栈是否为空和栈顶括号是否与之匹配。注意两个判断顺序不可以颠倒,不然会runtime error。时间复杂度为O(n)

class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;
        for(auto &ch:s)
        {
            if(ch == '('||ch == '{'||ch == '[')
            {
                stk.push(ch);
            }
            else if(ch == ')')
            {
                if(stk.empty()||stk.top() != '(')
                {
                    return false;
                }
                else
                {
                    stk.pop();
                }
            }
            else if(ch == '}')
            {
                if(stk.empty()||stk.top() != '{')
                {
                    return false;
                }
                else
                {
                    stk.pop();
                }
            }
            else if(ch == ']')
            {
                if(stk.empty()||stk.top() != '[')
                {
                    return false;
                }
                else
                {
                    stk.pop();
                }
            }
        }
        if(!stk.empty())
        {
            return false;
        }
        return true;
    }
};

Valid Parentheses - LeetCode

小结

一些栈的基本操作:

  • push(): 向栈内压入一个成员;
  • pop(): 从栈顶弹出一个成员;(注意要判断栈是否为空)
  • empty(): 如果栈为空返回true,否则返回false;
  • top(): 返回栈顶,但不删除成员;(注意要判断栈是否为空)
  • size(): 返回栈内元素的大小
上一篇:【LeetCode算法题库】Day7:Remove Nth Node From End of List & Valid Parentheses & Merge Two Lists


下一篇:Parentheses Matching