题目：有效的括号序列
难度：Easy
题目内容：
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
我的思路：数据结构——括号问题是经典的栈问题。
【因为这有三种括号，三个之间的嵌套比较复杂，所以不能简单地使用整形int作为判断（左括号++，右括号--），例如“([)]”这要是使用int那么就会判断正确。】
算法——利用一个栈，如果是左括号则直接放入，如果是右括号，pop栈顶看是否为对应左括号，否则return false；最后检查栈是否为空。
我的代码：
public boolean isValid(String s) {
char[] sc = s.toCharArray();
Stack<Character> stack = new Stack<Character>();
for(int i = 0; i<s.length(); i++) {
switch (sc[i]) {
case ')':
if (stack.empty() || stack.pop() != '(')
return false;
break;
case '}':
if (stack.empty() || stack.pop() != '{')
return false;
break;
case ']':
if (stack.empty() || stack.pop() != '[')
return false;
break;
default:
stack.push(sc[i]);
}
}
return stack.empty();
}
我的算法复杂度：时间——O（N） 空间——O（N）
编码过程出现问题：
1、一开始用的if else 比较繁琐，后来改的switch； 对于先peek判断再pop的，可以直接优化为判断相反条件的pop
例如：
if (!stack.empty() && stack.peek() == '[')
stack.pop();
else
return false;
break;
可以优化成：
if (stack.empty() || stack.pop() != '[')
return false;
break;
【其实没什么卵用。。】
2、pop()之前应该要判断栈是否为空，如果为空，也应该return false；
3、其实最开始可以加一个判断，如果s的长度为单数，则直接返回false。
参考答案代码：
public boolean isValid(String s) {
if ((s.length() & 1) == 1)
return false;
Stack<Character> stack = new Stack<Character>();
for (char c : s.toCharArray()) {
if (c == '(')
stack.push(')');
else if (c == '{')
stack.push('}');
else if (c == '[')
stack.push(']');
else if (stack.isEmpty() || stack.pop() != c)
return false;
}
return stack.isEmpty();
}
答案算法复杂度：时间——O（N） 空间——O（N）
答案思想：其实思想和我的那个差不多【强行不要脸】，不过这个方法利用了反向思维：如果当前是左括号，则放入对应的右括号，如果是右括号则pop栈顶是否是“自己”，否则return false。这样一来就减少了代码里对是否是对应左括号的判断。不过两者算法复杂度和意义上都一样，一个可读性好些，一个更加简练一些。