我试图解决这个问题。https://leetcode.com/problems/valid-parentheses/. 但是,我不知道在第二个for循环中是否可以比较s.charat(i)和stack.pop()。
基本上,我的方法是这样的。将整个字符串放入堆栈,然后使用stack.charat(i)遍历堆栈的前半部分,并使用stack.pop()将其与后半部分进行比较。我只是想知道在我的代码中可能会出什么问题,因为当我期望一个真值时得到了一个假值。我只是想弄明白我的观念是否有缺陷?
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
boolean done = false;
if(s.length() < 2)
return true;
for(int i = 0; i < s.length(); i++){
stack.push(s.charAt(i));
}
for(int i = 0; i < s.length()/2; i++){
if(s.charAt(i) == stack.pop())
done = true;
}
return done;
}
}
3条答案
按热度按时间qzlgjiam1#
而您的代码可能适用于字符串,例如“
{([])}
“和”(())
,你假设弦是对称的。一个有效的输入,例如“{()[]}
“不会传入您的代码,因为它不是对称的。修改代码以说明不对称性。提示:当字符是结束字符时,可能会弹出2个元素,如“)”“}”和“]”。lkaoscv72#
您的代码首先迭代到字符串的中间并填充堆栈,然后从中间到结尾弹出堆栈。换句话说,您隐式地假设一个有效字符串的前半部分是各种类型的左括号,第二部分是它们相应的右括号(例如。
([])
或者{[()]}
). 然而,这些并不是唯一有效的字符串-没有限制规定右括号不能跟在左括号后面,只要成对匹配-例如。,(()())
是有效字符串。与其假设字符串中的位置,不如遍历字符串,对于每个字符,如果是左括号,则将其推到堆栈中,如果是右括号,则弹出堆栈并比较两个字符:
ncecgwcz3#
您应该检查字符串中的括号是否匹配:对于
'('
有一个匹配的')'
. 但是,请注意'('
不等于字符')'
.您的代码正在检查字符串是否匹配一个模式,其中字符串的后半部分与字符串的前半部分相反,如
{[))[{
. 换句话说,您正在检查输入是否是回文。您应该采取的方法是只在堆栈中存储起始括号: