英文:
Not passing hidden tests: checking if a string can be rearranged to form a palindrome
问题
以下是翻译好的部分：
我正在尝试使用一个栈来完成这个问题：
给定一个字符串，找出它的字符是否可以重新排列成回文。
示例：
对于输入字符串 = "aabb"，输出应为
solution(inputString) = true。
我们可以重新排列 "aabb" 以形成 "abba"，这是一个回文。
然而，我的代码未通过两个隐藏测试，我不确定原因。
以下是我的代码：
boolean solution(String inputString) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < inputString.length(); i++) {
Character curr = inputString.charAt(i);
if (stack.contains(curr) == false) {
stack.push(curr);
}
else {
stack.pop();
}
}
if ((stack.size() == 0) || (stack.size() == 1)) {
return true;
}
return false;
}
我的代码有什么错误？
英文:
I am trying to complete this question using a Stack:
Given a string, find out if its characters can be rearranged to form a palindrome.
Example
For inputString = "aabb", the output should be
solution(inputString) = true.
We can rearrange "aabb" to make "abba", which is a palindrome.
However, my code isn't passing 2 of the hidden tests and I am unsure as to why.
Here is my code:
boolean solution(String inputString) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < inputString.length(); i++) {
Character curr = inputString.charAt(i);
if (stack.contains(curr) == false) {
stack.push(curr);
}
else {
stack.pop();
}
}
if ((stack.size() == 0) || (stack.size() == 1)) {
return true;
}
return false;
}
What is the error in my code?
答案1
得分: 0
False positive:
考虑字符串"cabcc"，它不能被重新排列成回文。您的代码将首先推入c，然后推入a，然后推入b，然后移除b（因为它是一个栈，并且在cab中找到了c），然后移除a（因为它在ca中找到了c）。
由于栈的长度为1，您的程序将输出cabcc可以被重新排列成回文，而实际上不能。
False negative
考虑字符串"acac"，它可以被重新排列成回文（例如acca）。您的代码将首先推入a，然后推入c，然后移除c（因为它是一个栈，并且在ac中找到了a），然后推入c。结果是栈包含ac。
由于栈的长度为2，您的程序将输出acac不能被重新排列成回文，但实际上可以。
How to fix
不要使用栈。我建议您使用映射（查看哈希映射）。
英文:
False positive:
Consider the string "cabcc", which cannot be rearranged to form a palindrome. Your code will first push c then push a then push b then remove b (since it is a stack and it found c in cab) then remove a (since it found c in ca).
Since the stack has a length of 1, your program will output that cabcc can be rearranged into a palindrome when it cannot.
False negative
Consider the string "acac", which can be rearranged to form a palindrome (acca for instance). Your code will first push a then push c then remove c (since it is a stack and it found a in ac) then push c. Resulting in a stack containing ac.
Since the stack has a length of 2, your program will output that acac cannot be rearranged into a palindrome when it can.
How to fix
Do not use a stack. I suggest you use a map (check out hashmaps).
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论