题目

类型：Stack

难度：简单

有效的括号 - 图1

解题思路

遍历给定的字符串 s。当遇到一个左括号时，放入栈顶。

当遇到一个右括号时，取出栈顶的左括号判断它们是否是相同类型的括号。如果不是相同的类型，或者栈中并没有左括号，那么字符串 s 无效，返回 False。为了快速判断括号的类型，使用HashMap存储每一种括号。HashMap的Key为右括号，Value为相同类型的左括号。

在遍历结束后，如果栈中没有左括号，返回True，否则返回 False。

注意：有效字符串的长度一定为偶数，因此如果字符串的长度为奇数，可以直接返回False，省去后续的遍历判断过程。

代码

  1. class Solution {
  2.     public boolean isValid(String s) {
  3.         int n = s.length();
  4.         if (n % 2 == 1) {
  5.             return false;
  6.         }
  8.         Map<Character, Character> pairs = new HashMap<Character, Character>() {{
  9.             put(')', '(');
  10.             put(']', '[');
  11.             put('}', '{');
  12.         }};
  13.         Deque<Character> stack = new LinkedList<Character>();
  14.         for (int i = 0; i < n; i++) {
  15.             char ch = s.charAt(i);
  16.             if (pairs.containsKey(ch)) {
  17.                 if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
  18.                     return false;
  19.                 }
  20.                 stack.pop();
  21.             } else {
  22.                 stack.push(ch);
  23.             }
  24.         }
  25.         return stack.isEmpty();
  26.     }
  27. }