题目信息
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()[]{}"
输出：true
示例 2：
输入：s = "{[]}"
输出：true
示例 3：
输入：s = "([)]"
输出：false
解题思路
- 暴力破解
- 无效操作分析
- 优化方法：
- 对应消除与先进后出的问题优先考虑栈的使用
- 奇数长度的字符串不用判断，一定不会完全匹配
- 考虑边界
- 编码实现：遍历所有字符
- 如果遇到了左括号，就把对应的右括号压栈
- 如果遇到了右括号
2.1 如果栈为空，该右括号无法形成闭合有效
2.2 栈不为空，弹出栈顶元素判断是否能够成闭合 - 遍历完毕，栈为空则全部括号都完成闭合匹配，不为空则还有未闭合的括号存在
代码
class Solution {
public boolean isValid(String s) {
// 奇数个绝对不可能对应匹配
if (s == null || s.trim().length() % 2 != 0) {
return false;
}
// 对应消除，首选栈
Stack<Character> stack = new Stack<>();
char[] chars = s.toCharArray();
// 遇到左括号便将对应右括号入栈
for (char c: chars) {
if(c == '(') {
stack.push(')');
} else if (c == '[') {
stack.push(']');
} else if (c == '{') {
stack.push('}');
} else if (stack.isEmpty() || stack.pop() != c) {
// 1. 栈为空，该右括号无法构成闭合
// 2. 弹栈并判断是否是预期的右括号
return false;
}
}
// 循环完毕，检查是否还有没有匹配到的，即栈是否为空
return stack.isEmpty();
}
}
题目来源：力扣（LeetCode）
题目链接：https://leetcode-cn.com/problems/valid-parentheses
商业转载请联系官方授权，非商业转载请注明出处。
