Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
Example 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true
分析：
给一串字符串仅包含大括号、中括号、小括号。判断这些括号是否合法，要求左右括号必须匹配，且嵌套合理。
此题为栈在括号匹配中的应用，从左到右扫描字符串，当读到左括号时，进栈，当读到右括号时，从栈中弹出一个元素，与这个右括号进行匹配，若匹配成功，继续读下去，若匹配失败，返回flase。
Java语言：
class Solution {
Map<Character, Character> map;
public Solution() {
this.map = new HashMap<>();
map.put(')', '(');
map.put(']', '[');
map.put('}', '{');
}
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (map.containsKey(c)) {
char top = stack.isEmpty() ? '#' : stack.pop();
if (top != map.get(c)) {
return false;
}
} else {
stack.push(c);
}
}
return stack.isEmpty();
}
}
