牛课题霸每日一题NC52题解Java8版本
题目描述
给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。
括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。
解题思路
括号匹配问题考虑栈结构来实现。合法的串左右括号都是成对出现，或者嵌套出现。
使用栈存储左括号，当遇到左括号则入栈，遇到右括号则出栈，检测弹出的左括号是否与当前右括号匹配，如果不匹配则不合法，如果匹配则继续检测下一个括号。
import java.util.*;
public class Solution {
/**
*
* @param s string字符串
* @return bool布尔型
*/
public boolean isValid (String s) {
// write code here
Deque<Character> stack = new LinkedList<>();
for(char ch: s.toCharArray()){
if(ch == '(' || ch == '{' || ch == '['){
stack.offerLast(ch);
}else{
Character top = stack.pollLast();
if(top == null){
return false;
}
if((ch == '}' && top == '{') ||
(ch == ']' && top == '[') ||
(ch == ')' && top == '(')){
continue;
}else{
return false;
}
}
}
return stack.isEmpty();
}
}