20. Valid Parentheses


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

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

**Input:** s = "()"
**Output:** true

Example 2:

**Input:** s = "()[]{}"
**Output:** true

Example 3:

**Input:** s = "(]"
**Output:** false

Constraints:

  • 1 <= s.length <= 104
  • s consists of parentheses only '()[]{}'.

这道题让我们验证输入的字符串是否为括号字符串,包括大括号,中括号和小括号。这里需要用一个栈,开始遍历输入字符串,如果当前字符为左半边括号时,则将其压入栈中,如果遇到右半边括号时,若此时栈为空,则直接返回 false,如不为空,则取出栈顶元素,若为对应的左半边括号,则继续循环,反之返回 false,代码如下:

解法一:

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

再来看一种写的更加简洁的方法,这里用个小 trick,之前是当遇到左括号时,把左括号压入栈,这样在出栈检测的时候,得判断当前遇到的右括号是哪种括号,是否跟栈顶的左括号匹配。而假如在压入栈的时候,我们直接将左括号对应的右括号压入栈,则在出栈检测的时候,就直接可以比较是否和栈顶元素相等了,因为都是右括号,这样写起来能相对简单一点,但是整体的思路还是相同的,参见代码如下:

解法二:

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

Github 同步地址:

https://github.com/grandyang/leetcode/issues/20

类似题目:

Remove Invalid Parentheses

Different Ways to Add Parentheses

Longest Valid Parentheses

Generate Parentheses

Check If Word Is Valid After Substitutions

Check if a Parentheses String Can Be Valid

Move Pieces to Obtain a String

参考资料:

https://leetcode.com/problems/valid-parentheses/

https://leetcode.com/problems/valid-parentheses/discuss/9178/Short-java-solution

https://leetcode.com/problems/valid-parentheses/discuss/9248/My-easy-to-understand-Java-Solution-with-one-stack

LeetCode All in One 题目讲解汇总(持续更新中…)

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,快快加入吧~)

知识星球 喜欢请点赞,疼爱请打赏❤️.

微信打赏

|

Venmo 打赏


—|—


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation