确定字符串是否为回文的最快方法

Question

我需要一种算法来验证一个字符串是否是回文（该字符串可以是由大写或小写字母、空格等组成的命题）。在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;
}

我使用 .toLowerCase() 函数将字符串转换成小写字母，但我不知道它对执行时间有多大影响。

同时，我也不知道如何以有效的方式解决标点符号和单词之间的空格问题。

- Bogdan Mursa

---

你的方法和其他有效的方法一样有效。虽然可以尝试寻找更高效的方法。 - Marco13

这不是一道作业题吗？ - Roland Tepp

@RolandTepp 这有什么关系吗？ - Duncan Jones

可能是Java中字符串翻转的重复问题。Reverse a string in Java - Anders R. Bystrup

“空格问题”是什么？空格应该完全忽略吗？ - maaartinus

Answer 1

我认为你可以只检查字符串reverse，对吧？

StringBuilder sb = new StringBuilder(str);
return str.equals(sb.reverse().toString());

或者，对于早于JDK 1.5的版本：

StringBuffer sb = new StringBuffer(str);
return str.equals(sb.reverse().toString());

- Andrey

---

@AndreyKnuppVital 哈哈，同意，你至少快了0.1秒！ - Joetjah

表达式 sb.toString() 返回 str，因此这是在浪费时间。 - maaartinus

@AndreyKnuppVital: :D:D:D 好的，我发现我的阅读能力可能需要升级。 - maaartinus

@maaartinus 关于这个话题：问题在于 String 没有 reverse() 方法。如果你尝试 str.equals(str.reverse())，会得到一个编译错误。此外，在 StringBuilder 对象上尝试 .equals() 会检查它们是否是相同的引用，而不是它们是否包含相同的字符串值。因此，我使用了 .toString()。 - Joetjah

@Joetjah：我的阅读能力可能比我想象的还要差，但不是这个问题。toString被使用了两次。你所说的是第二次使用。第一次只是返回原始的str。 - maaartinus

Answer 2

这样可以避免任何复制。函数isBlank和toLowerCase在你的问题中有些不明确，所以你可以按照自己的方式定义它们。这里只是一个例子：

boolean isBlank(char c) {
    return c == ' ' || c == ',';
}

char toLowerCase(char c) {
    return Character.toLowerCase(c);
}

不要担心方法调用的成本，这正是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;

尝试对此进行基准测试...我希望我的解决方案能够是最快的，但如果不进行测量，你就永远不会知道。

- maaartinus

---

这看起来是一个不错的解决方案。+1 - Keppil

Answer 3

就有效性而言，您的解决方案看起来很不错。

至于第二个问题，在开始测试之前，您可以删除所有空格和点等。

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)) {
...

- Keppil

---

.replaceAll("[\s.,]", "") - “\s”代表空格字符吗？ - Bogdan Mursa

“\s” 是空格字符的简写形式：[ \t\n\x0B\f\r]。 - Keppil

好的，伙计，谢谢。我认为这是我需要的一个解决方案。你有任何关于它如何影响时间和空间效率的想法吗？ - Bogdan Mursa

@BogdanMursa：使用 toLowerCase() 和正则表达式可能比动态处理要慢，但这有什么关系吗？ - maaartinus

@maaartinus 你说的“on the fly”是什么意思？ - Bogdan Mursa

@BogdanMursa: 我的意思是“不复制字符串”。你不需要额外的内存，如果你很幸运，在看完整个字符串之前就可以快速退出（例如对于 a....whatever....b）。请参见我的解决方案。 - maaartinus

Answer 4

有效并不等同于高效。

只要您考虑空格、特殊字符等，您的答案就是有效的。甚至重音符号也可能会有问题。

关于效率，toLowerCase的时间复杂度为O(n)，任何正则表达式解析也将是O(n)。如果您担心这一点，逐个字符转换和比较应该是最好的选择。

- rdllopes

---

那么像@Keppil在下面发布的解决方案是最佳选择吗？ - Bogdan Mursa

这就是我所说的问题。@maaartinus 目前是最快的解决方案。s.toLowerCase().replaceAll("[\s.,]", ""); - rdllopes

Answer 5

这是我的尝试：

这里是我的尝试：

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;
 }

- guest

Answer 6

在正常情况下：

 StringBuilder sb = new StringBuilder(myString);
 String newString=sb.reverse().toString();
 return myString.equalsIgnoreCase(newString); 

如果区分大小写，请使用：

StringBuilder sb = new StringBuilder(myString);
String newString=sb.reverse().toString();
return myString.equals(newString); 

- Raj Kumar

---

我认为原帖发布者正在寻找一个区分大小写的解决方案。 - Duncan Jones

Answer 7

以下是我使用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()));
   }
}

- Quan Nguyen