LeetCode(20)判断字符串合法括号
问题
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.
解决，考虑使用栈的先进后出特性来存放这个字符串。将字符串中字符从头开始入栈，如果栈空，则直接入栈。如果非空，则判断栈顶字符。根据不同的情况，判断是否与当前字符与栈顶字符是否构成一个完整的括号。如果是，则栈顶出栈，如果不是，则当前字符入栈。最后，返回栈是否非空，空，表明是合法括号字符串；非空，则有多余的字符不够成合法括号字符串。注意，对于参数的特性情况的判断。
java解决
class Solution {
public boolean isValid(String s) {
// 参数合法性判断
if(s == null){
return false;
}
int size = s.length();
if (size < 1 || s.equals("")) {
return true;
}
// 以链表作为栈
LinkedList<Character> stack = new LinkedList<Character>();
for (int i = 0; i < size; i++) {
char tmp = s.charAt(i);
if (stack.size() == 0) {
stack.push(tmp);
} else {
char top = stack.getFirst();
if (top == '(') {
if (tmp == ')') {
stack.pop();
} else {
stack.push(tmp);
}
} else if (top == '[') {
if (tmp == ']') {
stack.pop();
} else {
stack.push(tmp);
}
} else if (top == '{') {
if (tmp == '}') {
stack.pop();
} else {
stack.push(tmp);
}
} else {
return false;
}
}
}
return stack.isEmpty();
}
}