No.020：Valid Parentheses

问题：

Given a string containing just the characters '(', ')', '{', '}', '[' and ']',

determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

官方难度：

Easy

翻译：

给定一个字符串，仅包含字符：‘(’，‘)’，‘[’，‘]’，‘{’，‘}’。判断给定的字符串是不是一个合理的括号形式。括号必须顺序正确，诸如：“()”和“()[]{}”都是合理的，但是“(]”和“([)]”是不合理的。

首先判断字符串长度为0的特殊情况，返回true。
奇数长度的字符串，直接返回false。
定义2个字典方法，一个确定括号的方向，一个确定括号的级别。
这里特殊提一下，最初我认为类似“({})”不是合理的形式，但是提交时发现题目是允许这种形式的。
开始遍历字符串，维护一个左括号的集合。当遍历到左括号时，将这个字符加入集合；遍历到右括号时，首先判断左括号集合大小是否为0，若是，则返回false。然后比对左括号集合的最后一个元素与当前字符的括号级别和方向。
循环结束之后，若左括号集合大小不为0，返回false。
最后注意入参检查。

解题代码：

 1     public static boolean isValid(String str) {
 2         if (str == null) {
 3             throw new IllegalArgumentException("Input error");
 4         }
 5         // 0长度特殊处理
 6         if (str.length() == 0) {
 7             return true;
 8         }
 9         // 长度为奇数可以直接判断false
10         if (str.length() % 2 == 1) {
11             return false;
12         }
13         char[] array = str.toCharArray();
14         // 维护左括号的集合
15         List<Character> leftList = new ArrayList<>();
16         for (int i = 0; i < array.length; i++) {
17             if (getDirection(array[i]) == 1) {
18                 // 左括号处理
19                 leftList.add(array[i]);
20             } else if (getDirection(array[i]) == -1) {
21                 // 右括号处理
22                 if (leftList.size() == 0) {
23                     return false;
24                 } else {
25                     // 题目认为"({})"也是合理的形式
26                     Character last = leftList.get(leftList.size() - 1);
27                     if (getDirection(last) == -getDirection(array[i]) && getLevel(last) == getLevel(array[i])) {
28                         leftList.remove(leftList.size() - 1);
29                     } else {
30                         return false;
31                     }
32                 }
33             } else {
34                 throw new IllegalArgumentException("Input error");
35             }
36         }
37         // 循环结束之后判断leftList是否还有剩余
38         if (leftList.size() != 0) {
39             return false;
40         }
41         return true;
42     }
43 
44     // 括号级别
45     private static int getLevel(Character c) {
46         switch (c) {
47         case '{':
48         case '}':
49             return 3;
50         case '[':
51         case ']':
52             return 2;
53         case '(':
54         case ')':
55             return 1;
56         default:
57             return 0;
58         }
59     }
60 
61     // 括号方向
62     private static int getDirection(Character c) {
63         switch (c) {
64         case '{':
65         case '[':
66         case '(':
67             return 1;
68         case '}':
69         case ']':
70         case ')':
71             return -1;
72         default:
73             return 0;
74         }
75     }

isValid