摘要：
题目
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例1：
输入: "()"
输出: true
示例2：
输入: "()[]{}"
输出: true
示例3：
输入: "(]"
输出: false
示例4：
输入: "([)]"
输出: false
示例5：
输入: "{[]}"
输出: true
HashMap辅助的栈解法
构建一个 key 为开括号 '(','[','{' value为闭括号 ')'']''}' 的 HashMap。
遍历 String 字符串，当遇到开括号，由于将来有机会遇到与之对应的闭括号，故将其入栈。
当遇到闭括号，一旦它和栈顶的括号不匹配，可断言整体不是有效括号。（栈为空时，遇到的第一个若为闭括号也可看成与栈顶不匹配，但需做特殊处理）
当遍历完 String 字符串，中途没出现闭括号和栈顶字符不匹配的情况，此时若栈为空，则可断言之前入栈的开括号全部被匹配移除；若栈非空，可断言之前入栈的开括号没有找到匹配的闭括号，整体不属于有效括号。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution0x0 {
public static boolean isValid(String s) {
if (s == null) return true;
Map<Character, Character> map = new HashMap<>();
map.put(')', '(');
map.put(']', '[');
map.put('}', '{');
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char cha = s.charAt(i);
if (!map.containsKey(cha)) {
stack.push(cha);
}
else {
char top = stack.isEmpty() ? '!' : stack.pop();
if (map.get(cha) != top) return false;
}
}
return stack.isEmpty();
}
}
|
纯栈解法
基本思路与上述方法一致，只是在判断闭括号栈顶元素时用一个小技巧代替 HashMap。
遍历字符串，当遇到开括号时，把相对应的闭括号入栈。比如遇到 (，把 ) 入栈。这样，当下一个若是闭括号我们要那它和栈顶元素比较的话，可以不查 HashMap 而是直接比较是否相等。若相等，则是一对。继续循环。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution0x1 {
public boolean isValid(String s) {
if (s == null) return true;
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char cha = s.charAt(i);
if (cha == '(') stack.push(')');
else if (cha == '[') stack.push(']');
else if (cha == '{') stack.push('}');
else if (stack.isEmpty() || cha != stack.pop()) return false;
}
return stack.isEmpty();
}
}
|