20. Valid Parentheses

置顶

Created At : 2021-04-07 23:39

Count:729 Views 👀 :

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

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
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/