Question
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.
看了题目以为“[{}]"这种是不合法的，结果这题这种string是合法的。
拿到题目之前已经知道这道题要用Stack来解，就直接上LinkedList了。
Solutions
以下是鄙人的渣解，思想就是用linkedList构成一个Stack结构的桶，然后每判断一个字符
- 是“)”,"]","}"，
- 桶为空, 扔进桶
- 不空，判断桶的第一个字符是否为“)”,"]","}"对应的小伙伴
- 是，删除小伙伴
- 不是, 返回false
- 不是“)”,"]","}, 扔进桶
public class Solution {
public boolean isValid(String s) {
if (s.length() % 2 != 0)
return false;
LinkedList<Character> list = new LinkedList();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == ')' || s.charAt(i) == ']' || s.charAt(i) == '}') {
if (list.size() > 0 && ((list.getFirst() - 'A' == s.charAt(i) - 1 - 'A')
|| (list.getFirst() - 'A' == s.charAt(i) - 2 - 'A'))) {
list.removeFirst();
} else if (list.size() > 0){
return false;
} else {
list.addFirst(s.charAt(i));
}
} else {
list.addFirst(s.charAt(i));
}
}
if (list.size() > 0) {
return false;
} else {
return true;
}
}
}
Points
- ASCII码表
一开始以为{}，[],（)在表里都是连续的，结果代码错误。实际上表里只有（）是连续的，[]和{}都被第三者插足。
ascii01.png
- LeetCode Runtime
不是很懂LeetCode是怎么计算的，我相同的代码，试了两次一个1ms一个2ms，是不是再试一次就能达成0ms了？
屏幕快照 2016-03-16 上午10.48.08.png
屏幕快照 2016-03-16 上午10.48.22.png
TO DO
- Stack和LinkedList
