英文:
Can someone explain what is wrong with my approach?
问题
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;
}
}
英文:
I was trying to attempt this problem. https://leetcode.com/problems/valid-parentheses/. However, I was confused if in the second for loop I can compare s.charAt(i) and stack.pop().
Basically, my approach was such. Push the entire string to a stack, and then run through the first half of the stack using stack.charAt(i) and compare it to the second half using stack.pop(). I just wanted to know what might be going wrong in my code as I get a false value when expecting a true value. I am just trying to understand if my concept is flawed or not?
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;
}
}
答案1
得分: 1
虽然您的代码可能适用于诸如“{([])}
”和“(())
”之类的字符串,但您假设这些字符串将是对称的。一个有效的输入,例如“{()[]}
”,将无法在您的代码中通过,因为它不是对称的。修改您的代码以考虑非对称情况。
提示:当字符是闭合字符(例如“)”、“}”和“]”)时,也许可以弹出2个元素。
英文:
While your code might work for strings such as "{([])}
" and "(())
", you are assuming that the strings will be symmetrical. A valid input such as "{()[]}
" will not pass in your code because it is not symmetrical. Modify your code to account for asymmetry.
Hint: maybe pop 2 elements when the character is a closing character such as ")" "}" and "]".
答案2
得分: 1
你需要检查字符串中的括号是否匹配:对于一个 '('
,应有一个匹配的 ')'
。然而需要注意的是,字符 '('
并不等同于字符 ')'
。
你的代码在检查字符串是否符合一种模式,即字符串的后半部分是前半部分的倒序,比如 {[))[{
。换句话说,你在检查输入是否为一个*回文*。
你应该采取的方法是只将起始括号存储在栈中:
for(int i = 0; i < s.length(); i++){
if s.charAt(i) 是一个开括号:
将 s.charAt(i) 压入栈中;
否则:
从栈中"弹出"一个字符;
如果它是 '(',确保 s.charAt(i) 是 ')'
如果它是 '[',确保 s.charAt(i) 是 ']'
如果它是 '{',确保 s.charAt(i) 是 '}'
}
英文:
You are supposed to check if the parentheses in a string match: that for a '('
there is a matching ')'
. However, note that the character '('
is not equal to the character ')'
.
Your code is checking if the string matches a pattern where the second half of the string is the first half of the string in reverse, like {[))[{
. In other words, you're checking if the input is a palindrome.
The approach you should take is storing only the starting brackets in the stack:
for(int i = 0; i < s.length(); i++){
if s.charAt(i) is an open bracket:
stack.push(s.charAt(i));
else:
"pop" a character from stack
if it's '(' make sure that s.charAt(i) is ')'
if it's '[' make sure that s.charAt(i) is ']'
if it's '{' make sure that s.charAt(i) is '}'
}
答案3
得分: 0
你的代码首先迭代到字符串的中间并填充堆栈,然后从中间到结尾并弹出堆栈。换句话说,你隐含地假设有效字符串的前半部分是各种类型的开放括号,而后半部分是它们对应的闭合括号(例如,([])
或 {[()]}
)。然而,这些不是唯一有效的字符串——并没有限制说闭合括号后面不能紧跟着开放括号,只要配对匹配——例如,(()())
是一个有效的字符串。
与其对字符串内部位置进行假设,你应该遍历整个字符串,对于每个字符,如果它是开放括号,则将其压入堆栈;如果它是闭合括号,则弹出堆栈并进行比较:
private static final Map<Character, Character> PARENS = new HashMap<>();
static {
PARENS.put('(', ')');
PARENS.put('[', ']');
PARENS.put('{', '}');
}
public static boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); ++i) {
char ch = s.charAt(i);
if (PARENS.containsKey(ch)) {
stack.push(ch);
} else {
if (stack.isEmpty()) {
return false;
}
char match = stack.pop();
if (ch != PARENS.get(match)) {
return false;
}
}
}
return stack.isEmpty();
}
英文:
Your code first iterates up to the middle of the string and populates the stack, and then from the middle to the end and pops the stack. In other words, you're implicitly assuming that the first half of a valid string is opening parentheses of various types, and the second is their corresponding closing parentheses (e.g. ([])
or {[()]}
). However, these aren't the only valid strings - there is no limitation that states that a closing parenthesis can't be followed by an opening one, as long as the pairs are matched - e.g., (()())
is a valid string.
Instead of making assumptions on the position within the string, you should iterate over the string, and for each character, if it's an opening parenthesis push it to the stack, and if it's a closing parenthesis pop the stack and compare the two:
private static final Map<Character, Character> PARENS = new HashMap<>();
static {
PARENS.put('(', ')');
PARENS.put('[', ']');
PARENS.put('{', '}');
}
public static boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); ++i) {
char ch = s.charAt(i);
if (PARENS.containsKey(ch)) {
stack.push(ch);
} else {
if (stack.isEmpty()) {
return false;
}
char match = stack.pop();
if (ch != PARENS.get(match)) {
return false;
}
}
}
return stack.isEmpty();
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论