每天AC系列(六):有效的括号
2 栈
这是栈的典型应用,括号匹配,当然不需要直接使用栈,使用一个StringBuilder即可:
if(s.isEmpty())
return true;
char a = s.charAt(0);
if (a != "(" && a != "[" && a != "{")
return false;
StringBuilder t = new StringBuilder();
int len = -1;
for(char c:s.toCharArray())
{
if(c == "(" || c == "[" || c == "{")
{
t.append(c);
++len;
}
else
{
if(len == -1)
return false;
char cc = t.charAt(len);
if(
(c == ")" && cc != "(")
||
(c == "]" && cc != "[")
||
(c == "}" && cc != "{")
)
return false;
t.deleteCharAt(len--);
}
}
return len == -1;
首先判断是否为空,再判断第一个字符,然后进入逐个循环判断,若表示左边的括号则append,若表示右边的括号首先判断len,然后取出len处字符进行判断是否匹配,不匹配直接返回false,匹配的话则删除这个字符.最后根据len是否为-1返回最终结果.
3 优化
其实就是简化一下代码,直接开辟一个大的空间,不需要进行append与delete,只需移动栈顶指针.栈顶指针从1开始,若从0开始的话对于"]"这种情况会报下标越界错误,压栈就是++p,压入字符,出栈直接- - p,然后判断是否匹配即可.
char[] t = new char[s.length() + 1];
int p = 1;
for (char c : s.toCharArray())
{
if (c == "(" || c == "[" || c == "{")
t[p++] = c;
else
{
--p;
if ((c == ")" && t[p] != "(") || (c == "]" && t[p] != "[") || (c == "}" && t[p] != "{"))
return false;
}
}
return p == 1;