LeetCode 20 有效的括号
题目:
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([)]"
输出：false
示例 5：
输入：s = "{[]}"
输出：true
提示：
1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成
题解:
此题我们使用数据结构中的栈结构来巧解此题
我们知道，一个有效的括号组合有以下特性
1.括号组的数量一定是偶数
2.括号组的数量如果是0则一定有效
3.每种类型的左括号和右括号数量相同
4.每一对括号内要么没有其他括号组，如果有，其他括号组一定也是有效括号组
我们按照以下规则处理:
剪枝
1.如果括号组数量是奇数直接返回False
2.如果括号组的数量如果是0直接返回True
遍历
1.如果括号是左括号，直接入栈
2.如果括号是右括号:
a.如果栈顶括号是与之匹配的左括号,栈顶括号出栈
b.其他所有情况直接返回False
3.如果括号组全部匹配完毕返回True
图解:
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public boolean isValid(String s) {
int len = s.length();
if (len == 0) return true;
if (len % 2 != 0) return false;
char[] chars = s.toCharArray();
Stack<Character> stack = new Stack<>();
String signal = "{[(}])";
for (int i = 0; i < len; i++) {
int index = signal.indexOf(chars[i]);
if (index < 3) {
stack.add(chars[i]);
} else {
if (stack.isEmpty()) return false;
char c = stack.pop();
if (c != signal.charAt(index - 3)) {
return false;
}
}
}
return stack.isEmpty();
}
|