Description
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.
Discussion
括号匹配问题。这个问题我们可以使用一个栈myStack来完成。当元素为左括号时，把该元素压栈。当元素为右括号时，弹出栈顶元素并与该元素进行比较，若不是一对，则整个字符串不匹配。最后我们还需要判断一下栈是否为空，若不为空，说明有多余左括号没有配对，则整个字符串不匹配。
算法的时间复杂度为O(n)。
C++ Code
class Solution {
public:
bool isValid(string s) {
stack<char> myStack; //定义一个栈，当前字符若是左括号，则压栈；若是右括号，则弹栈并进行比较
//对字符串的每个元素进行判断
for(int i = 0; i < s.length(); i++)
{
//当前字符若是左括号，则压栈
if(s[i] == '(' || s[i] == '[' || s[i] == '{')
{
myStack.push(s[i]);
continue;
}
//当前字符若是右括号，且栈内没有元素，则不匹配
if(myStack.size() == 0)
{
return false;
}
//当前字符若是右括号，从栈中弹出一个元素进行比较
switch(s[i])
{
case ')':
if(myStack.top() == '(')
myStack.pop();
else
return false;
break;
case ']':
if(myStack.top() == '[')
myStack.pop();
else
return false;
break;
case '}':
if(myStack.top() == '{')
myStack.pop();
else
return false;
break;
}
}
//最后若是栈内还有元素，说明有多余左括号
if(myStack.size() == 0)
return true;
else
return false;
}
};