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.
思路:用栈。要注意的一点是,当读到了右括号时,在判断栈顶是否是对应的左括号前,要先确定栈是否为空。
1 class Solution { 2 public: 3 bool isValid(string s) { 4 stack<char> va; 5 for (auto i : s) 6 { 7 if (i == '(' || i == '{' || i == '[') 8 va.push(i); 9 else if (va.empty()) return false; 10 else if (i == ')' && va.top() != '(') 11 return false; 12 else if (i == '}' && va.top() != '{') 13 return false; 14 else if (i == ']' && va.top() != '[') 15 return false; 16 else va.pop(); 17 } 18 return va.empty(); 19 } 20 };