一、题目
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
二、示例
2.1> 示例 1：
【输入】s = "()"
【输出】true
2.2> 示例 2：
【输入】s = "()[]{}"
【输出】true
2.3> 示例 3：
【输入】s = "(]"
【输出】false
提示：
-
1<= s.length <=10^4 -
s仅由括号 '()[]{}' 组成
三、解题思路
根据题目描述，我们需要校验给定的字符串s是否是有效字符串，这里的“有效”就是通过是否是完整括号来决定的（小括号、中括号、大括号）。那么，对于这种字符“配对”的题目，我们就很容易能够想到，可以采用堆栈的方式进行解题。那么此处，我们可以采用Stack类来提供堆栈能力的支持，也可以使用双向队列Deque来提供堆栈能力的支持，由于在LeetCode的执行效率中，Deque的执行效率是要比Stack高的，所以我建议大家采用Deque来模拟堆栈行为。
基本的解题思想确定了之后，我们就可以通过遍历字符串 + 堆栈来进行解题了。假设我们将遍历到字符串s的字符称为c，那么此处入栈我们指定了3个约束条件：
【条件1】如果遍历的字符c等于'
('，那么我们就将字符‘)’执行入栈操作；
【条件2】如果遍历的字符c等于'['，那么我们就将字符‘]’执行入栈操作；
【条件3】如果遍历的字符c等于'{'，那么我们就将字符‘}’执行入栈操作；
那么，针对不满足以上3个条件，我们只需要执行如下判断：
【判断1】将
stack栈顶元素弹出，如果它等于c，则继续执行；
【判断2】将stack栈顶元素弹出，如果它不等于c，则终止执行，返回false；
好了，以上就是本题的解题思路了，为了方便大家理解，我们以输入s = "()[){}"为例，看一下其具体的执行过程是怎么样的。具体详情，请见下图所示：
四、代码实现
class Solution {
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') stack.addLast(')');
else if (c == '[') stack.addLast(']');
else if (c == '{') stack.addLast('}');
else if (stack.isEmpty() || c != stack.removeLast()) return false;
}
return stack.isEmpty();
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
