Valid Parentheses
Given a string containing just the characters '('
, ')'
,
'{'
, '}'
, '['
and ']'
, determine if the input string is valid.
The brackets must close in the correct order, "()"
and "()[]{}"
are all valid but
"(]"
and "([)]"
are not.
思路:
典型的堆栈数据结构问题。在碰到左括号的时候入栈,右括号的时候出栈。最后栈如果是空,则表明左右括号对称。
题解:
class Solution { public: char counterPart(const char ch) { switch(ch) { case '{': return '}'; case '[': return ']'; case '(': return ')'; default: return 0; } } bool isValid(string s) { stack<char> parenthesis; for(auto ch: s) if (ch == '(' || ch == '[' || ch == '{') parenthesis.push(ch); else if (!parenthesis.empty() && ch == counterPart(parenthesis.top())) parenthesis.pop(); else return false; return parenthesis.empty(); } };