Java 判断字符串是否为回文的最快方法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/21403782/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
The fastest method of determining if a string is a palindrome
提问by Bogdan Mursa
I need an algorithm that verify with the fastest possible execution time, if a string is a palindrome ( the string can be a proposition with uppercase or lowercase letter, spaces etc.). All of this in Java. I got a sample :
如果字符串是回文（字符串可以是带有大写或小写字母、空格等的命题），我需要一种算法以尽可能快的执行时间进行验证。所有这些都在 Java 中。我得到了一个样本：
bool isPalindrome(string s) {
int n = s.length();
s = s.toLowerCase();
for (int i = 0; i < (n / 2) + 1; ++i) {
if (s.charAt(i) != s.charAt(n - i - 1)) {
return false;
}
}
return true;
}
I transformed the string in lowercase letter using .toLowerCase()function, but I don't know how much it affects the execution time .
我使用.toLowerCase()函数将字符串转换为小写字母，但我不知道它对执行时间的影响有多大。
And as well I don't know how to solve the problem with punctuation and spaces between words in a effective way.
而且我不知道如何以有效的方式解决标点符号和单词之间的空格问题。
回答by CentaurWarchief
I think you can just check for string reverse, not?
我想你可以只检查 string reverse，不是吗？
StringBuilder sb = new StringBuilder(str);
return str.equals(sb.reverse().toString());
Or, for versions earlier than JDK 1.5:
或者，对于早于 JDK 1.5 的版本：
StringBuffer sb = new StringBuffer(str);
return str.equals(sb.reverse().toString());
回答by Keppil
Your solution seems just fine when it comes to effectiveness.
您的解决方案在有效性方面似乎很好。
As for your second problem, you can just remove all spaces and dots etc before you start testing:
至于您的第二个问题，您可以在开始测试之前删除所有空格和点等：
String stripped = s.toLowerCase().replaceAll("[\s.,]", "");
int n = stripped.length();
for (int i = 0; i < (n / 2) + 1; ++i) {
if (stripped.charAt(i) != stripped.charAt(n - i - 1)) {
...
回答by rdllopes
Effective is not the same of efficient.
有效不等于高效。
Your answer is effective as long you consider spaces, special characters and so on. Even accents could be problematic.
只要您考虑空格、特殊字符等，您的答案就有效。甚至口音也可能有问题。
About efficiency, toLowerCase is O(n) and any regexp parsing will be O(n) also. If you are concerning about that, convert and compare char by char should be the best option.
关于效率，toLowerCase 是 O(n) 并且任何正则表达式解析也将是 O(n)。如果您对此感到担忧，按字符转换和比较字符应该是最好的选择。
回答by Raj Kumar
In normal cases :
在正常情况下：
StringBuilder sb = new StringBuilder(myString);
String newString=sb.reverse().toString();
return myString.equalsIgnoreCase(newString);
In case of case sensitive use :
在区分大小写的情况下使用：
StringBuilder sb = new StringBuilder(myString);
String newString=sb.reverse().toString();
return myString.equals(newString);
回答by maaartinus
This avoids any copying. The functions isBlankand toLowerCaseare rather unspecified in your question, so define them the way you want. Just an example:
这避免了任何复制。功能isBlank和toLowerCase在您的问题中未指定，因此请按照您想要的方式定义它们。只是一个例子：
boolean isBlank(char c) {
return c == ' ' || c == ',';
}
char toLowerCase(char c) {
return Character.toLowerCase(c);
}
Don't worry about the costs of method calls, that's what the JVM excels at.
不用担心方法调用的成本，这正是 JVM 所擅长的。
for (int i = 0, j = s.length() - 1; i < j; ++i, --j) {
while (isBlank(s.charAt(i))) {
i++;
if (i >= j) return true;
}
while (isBlank(s.charAt(j))) {
j--;
if (i >= j) return true;
}
if (toLowerCase(s.charAt(i)) != toLowerCase(s.charAt(j))) return false;
}
return true;
Try to benchmark this... I'm hoping mu solution could be the fastest, but without measuring you never know.
尝试对此进行基准测试...我希望 mu 解决方案可能是最快的，但如果不进行测量，您永远不会知道。
回答by Quan Nguyen
Here's some insight to my way of detecting a palindrome using Java. Feel free to ask question :) Hope I could help in some way....
这是我使用 Java 检测回文的方法的一些见解。随意提问:) 希望我能以某种方式提供帮助....
import java.util.Scanner;
public class Palindrome {
public static void main(String[]args){
if(isReverse()){System.out.println("This is a palindrome.");}
else{System.out.print("This is not a palindrome");}
}
public static boolean isReverse(){
Scanner keyboard = new Scanner(System.in);
System.out.print("Please type something: ");
String line = ((keyboard.nextLine()).toLowerCase()).replaceAll("\W","");
return (line.equals(new StringBuffer(line).reverse().toString()));
}
}
回答by guest
Here is my try:
这是我的尝试：
public static boolean isPalindrome(String s)
{
int index1 = 0;
int index2 = s.length() -1;
while (index1 < index2)
{
if(s.charAt(index1) != s.charAt(index2))
{
return false;
}
index1 ++;
index2 --;
}
return true;
}
