20. Valid Parentheses
Given a string 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.
Note that an empty string is also considered valid.
Example 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true
思路
应该说非常简单了,第一时间想到的就是栈:
- 如果为空,则入栈
- 碰到右括号,判断栈顶是否是其对应的左括号,如果是,则出栈,不是,则继续入栈
- 最后如果栈为空,表示括号对一一匹配,返回true,否则为false
代码
class Solution {
public:
bool isValid(string s) {
stack<char> stk;
for (auto c : s)
if (!stk.empty() && (\
(c == ')' && stk.top() == '(') || \
(c == ']' && stk.top() == '[') || \
(c == '}' && stk.top() == '{')))
stk.pop();
else stk.push(c);
return stk.empty();
}
};