Version: Next

20.有效的括号

https://leetcode-cn.com/problems/valid-parentheses/

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。

Example 1:
Input: s = "()"
Output: true

Example 2:
Input: s = "()[]{}"
Output: true

Example 3:
Input: s = "(]"
Output: false

Example 4:
Input: s = "([)]"
Output: false

Example 5:
Input: s = "{[]}"
Output: true

思路与实现

直接匹配字符串

  • 循环找到字符串中的()，{}，[]，将它们都替换为""空字符串
  • 跳出循环说明字符串中不包含(),[],{}
  • 最终看字符串是否为""空字符串
    • 空：说明括号合法
    • 非空：说明不合法
public boolean isValid1(String s) {
while (s.contains("{}") || s.contains("()") || s.contains("[]")) {
s = s.replace("{}", "");
s = s.replace("()", "");
s = s.replace("[]", "");
}
return s.isEmpty();
}

使用栈

  • 遇到左括号就直接入栈
  • 遇到右括号时，立即拿出栈顶元素与之匹配，成功则弹出栈顶元素，然后新栈顶和下一个右字符进行比较； 匹配失败则return false
  • 最终栈为空，说明全部匹配
  • 最终栈不会空，说明匹配失败
边界情况

如果遇到右括号时，栈是空的，说明根本没有左括号

private Stack<Character> stack = new Stack<>();
public boolean isValid(String s) {
if (!stack.isEmpty()) stack.clear(); // 如果栈中已经有值，先清空
for (int i = 0; i < s.length(); i++) { // 遍历字符串中的字符
char c = s.charAt(i); // 取出字符
if (c == '(' || c == '[' || c == '{') { //如果字符是左括号
stack.push(c);
} else { // 如果不是左括号，就当成是右括号
// 把栈顶拿出来进行匹配
if (stack.isEmpty()) // 如果栈是空的，说明根本没有左括号
return false; //直接返回不匹配
Character left = stack.pop(); // 此时右括号为c
if (left == '(' && c != ')') return false;
if (left == '[' && c != ']') return false;
if (left == '{' && c != '}') return false;
}
}
return stack.isEmpty();
}
info

借助HashMap，建立左右括号字典，来简化代码

private Stack<Character> stack = new Stack<>();
private Map<Character, Character> map = new HashMap<>();
public _20有效的括号() {
map.put('(', ')');
map.put('[', ']');
map.put('{', '}');
}
public boolean isValid(String s) {
if (!stack.isEmpty()) stack.clear(); // 如果栈中已经有值，先清空
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (map.containsKey(c)) { // 如果字符是左括号之一
stack.push(c); //入栈
} else { // 不是左括号，就认为是右括号
// 弹出栈顶为左，当前c为右，尝试匹配
if (stack.isEmpty()) return false; // 如果栈为空，说明根本没左括号
Character left = stack.pop();
// c代表的右， 不等于， 左括号应当对应的右，就返回匹配失败
if (c != map.get(left)) return false;
}
}
return stack.isEmpty();
}

测试

public static void main(String[] args) {
_20有效的括号 obj = new _20有效的括号();
System.out.println("obj.isValid(\"{}\") = " + obj.isValid("{}"));
System.out.println("obj.isValid(\"{}[]\") = " + obj.isValid("{}[]"));
System.out.println("obj.isValid(\"({)}\") = " + obj.isValid("({)}"));
System.out.println("obj.isValid(\"(())\") = " + obj.isValid("(())"));
System.out.println("obj.isValid(\"({})\") = " + obj.isValid("({})"));
}
运行结果
obj.isValid("{}") = true
obj.isValid("{}[]") = true
obj.isValid("({)}") = false
obj.isValid("(())") = true
obj.isValid("({})") = true