一、题目描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([)]"
输出：false
示例 5：
输入：s = "{[]}"
输出：true
提示：
1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成
二、思路讲解
有效括号类的问题基本上都可以用栈来解决，因为括号匹配的顺序刚好符合栈先进后出的特性。
遍历字符串，当遇到左括号时，就入栈；当遇到右括号时，就弹出，如果弹出的括号和当前的右括号不匹配，则说明出错了。
当遍历完字符串后，如果栈不为空，说明有左括号落单了，说明出错；如果栈为空，说明匹配正确。
还可以再简化一下：如果遇到了左括号，就压入对应的右括号（比如遇到'('，就压入')' ）。那么遇到右括号时只需弹出元素，比对弹出元素与当前括号是否一致就行了，这样就免去了几个if判断。
三、Java代码实现
class Solution { public boolean isValid(String s) { Stack<Character> stack = new Stack<>(); for(char c : s.toCharArray()){ if(c=='('){ stack.push(')'); } else if(c=='['){ stack.push(']'); } else if(c=='{') { stack.push('}'); } else if(stack.isEmpty() || stack.pop()!=c){ return false; } } //如果栈不为空，说明有左括号落单了；如果栈为空，说明括号正确 return stack.isEmpty(); } }
四、C++代码实现
class Solution { public: bool isValid(string s) { stack<char> stack; char temp; for (char ss : s) { if (ss == '(') { stack.push(')'); }else if (ss == '[') { stack.push(']'); }else if (ss == '{') { stack.push('}'); }else if (stack.empty()) { return false; }else if (stack.top() != ss) { return false; }else { stack.pop(); } } if (stack.empty()) { return true; }else { return false; } } };
五、时空复杂度分析
时间复杂度： O(N)
空间复杂度： O(N)
