20. 有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。

  2. 左括号必须以正确的顺序闭合。

    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('}', '{');     //用键值对的形式存储三种括号，右括号为key 左为value
    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)) {  //碰到右括号，找key对应的value
    17.              if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
    18.                                   //取栈顶元素，但不出  找键值对里面包不包括
    19.                  return false;
    20.              }
    21.              stack.pop();  //能匹配就出栈
    22.          } else {
    23.              stack.push(ch);   //遇到左括号进栈
    24.          }
    25.      }
    26.      return stack.isEmpty();   //看最后是否为空
    27.  }
    28. }
  • 先判断边界条件（成对的括号是否满足偶数个）
  • 把题目里面出现的括号存在一个hashmap里面，key是右括号，value是左
  • 循环遍历字符串中的元素，左括号进栈，右括号判断
  • 看最后是否为空