题目:
给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
*
示例 1:
输入:s = “()”
输出:true
*
示例 2:
输入:s = “()[]{}”
输出:true
括号配对,可以利用栈结构,因为栈是先进后出,也就是后进先出的。每次对栈弹出的元素以及栈是否为空进行判断就OK了。当然奇数长度肯定不对的
import java.util.Stack;
class Solution {
public boolean isValid(String s) {
int n = s.length();
if (n % 2 == 1) {
return false;
}
Stack<Character> stack = new Stack<>();
char temp;
for(char i:s.toCharArray()){
if(i == '(' || i == '[' || i == '{'){
stack.push(i);
}else if(i == ')'){
if(stack.isEmpty())
{
return false;
}
temp = stack.pop();
if(temp != '(')
{
return false;
}
}else if(i == ']'){
if(stack.isEmpty())
{
return false;
}
temp = stack.pop();
if(temp != '[')
{
return false;
}
}else if(i == '}'){
if(stack.isEmpty())
{
return false;
}
temp = stack.pop();
if(temp != '{')
{
return false;
}
}
}
if(stack.isEmpty())
return true;
else
return false;
}
}
看起来不太舒服所以又优化了一下
import java.util.Stack;
class Solution {
public boolean isValid(String s) {
int n = s.length();
if (n % 2 == 1) {
return false;
}
Stack<Character> stack = new Stack<>();
char temp;
for(char c:s.toCharArray()){
if(c == '(' || c == '[' || c == '{') // 入栈
stack.push(c);
else
{
if(stack.isEmpty()) //为空肯定是错的
return false;
temp = stack.pop(); // 弹出栈顶元素
if(c == ')' && temp != '(') //判断是否匹配
return false;
if(c == ']' && temp != '[')
return false;
if(c == '}' && temp != '{')
return false;
}
}
return stack.isEmpty();
}
}
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/Y_peak/article/details/120359228
内容来源于网络,如有侵权,请联系作者删除!