15_20. 有效的括号
题目描述：
解题思路：
- 利用栈，遇到左括号入栈，有括号就出栈，查看二者是否匹配。对java了解的不深入，不知道有自带的栈，自己写了链表实现的栈。
- 题解是利用栈，java有自带的栈结构，而且可以使用HashMap来匹配左右括号，不需要if条件判断。
代码：
自己实现的栈
//自己实现的栈
class Solution {
public boolean isValid(String s) {
if (s == null) {
return true;
}
int len = s.length();
Stack stack = new Stack();
for (int i = 0; i < len; i++) {
char c = s.charAt(i);
swtich (c){
case c.equal('(') :
stack.push(c);
break;
case c == '[' :
stack.push(c);
break;
case c == '{' :
stack.push(c);
break;
defalut :
if (stack.isEmpty()) {
return false;
}
ListNode node = stack.pop();
if (c == '(' && node.val == ')'){
}else if (c == '[' && node.val == ']'){
}else if (c == '{' && node.val == '}'){
}else {
return false;
}
break;
}
}
if (stack.isEmpty()){
return true;
}
return false;
}
}
class Stack {
ListNode top;
Stack (){};
Stack (ListNode top) {
this.top = top;
}
private boolean push (String s) {
ListNode node = new ListNode(s);
node.next = top;
top = node;
}
private boolean isEmpty (){
if (top == null){
return true;
}
return false;
}
private ListNode pop (){
if (isEmpty) {
return null;
}
ListNode node = pop;
pop = pop.next;
return node;
}
}
class ListNode {
String val;
ListNode next;
ListNode (){};
ListNode (String val){
this.val = val;
}
ListNode (String val, ListNode next) {
this.val = val;
this.next = next;
}
}
题解中的栈和HashMap
//题解中的栈和HashMap
class Solution {
public boolean isValid(String s) {
int n = s.length();
if (n % 2 != 0) {
return false;
}
HashMap pairs = new HashMap<>();
pairs.put(')','(');
pairs.put('}','{');
pairs.put(']','[');
Deque stack = new LinkedList();
for (int i = 0; i < n; i++){
char ch = s.charAt(i);
if (pairs.containsKey(ch)){
if (stack.isEmpty() || stack.peek() != pairs.get(ch)){
return false;
}
stack.pop();
}else {
stack.push(ch);
}
}
return stack.isEmpty();
}
}