# 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 `'()[]{}'`.

``````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();
}
};
``````

``````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

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 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation