string - 为什么我们不能一次性可靠地测试回文

Question

我遇到了“回文”的概念。我尝试通过阅读维基百科来理解

http://en.wikipedia.org/wiki/Palindrome#Computation_theory

这段话引起了我的注意

This means that it is impossible for a computer with a finite amount of memory to reliably test for palindromes on one pass.

我想测试一个给定的字符串是否是“回文”是不是很简单？我出来了一个快速代码。

public class Utils {
    private static final String SPECIAL_CHARACTERS_REGEX = "[\\s!,]";

    private static String removeSpecialCharacters(String string) {
        return string.replaceAll(SPECIAL_CHARACTERS_REGEX, "");
    }

    public static boolean isPalindrome(String string) {
        String str = string.toLowerCase();
        str = removeSpecialCharacters(str);

        if (str.isEmpty()) {
            return false;
        }

        int head = 0;
        int tail = str.length() - 1;
        while (head < tail) {
            char h = str.charAt(head);
            char t = str.charAt(tail);

            if (h != t) {
                return false;
            }

            head++;
            tail--;
        }

        return true;
    }
}

乍一看似乎工作正常。

public static void main(String[] args) {
    String s = "";
    System.out.println(s + " -> " + Utils.isPalindrome(s)); // false

    s = "1";
    System.out.println(s + " -> " + Utils.isPalindrome(s)); // true

    s = "12";
    System.out.println(s + " -> " + Utils.isPalindrome(s)); // false

    s = "123";
    System.out.println(s + " -> " + Utils.isPalindrome(s)); // false

    s = "taco cat";
    System.out.println(s + " -> " + Utils.isPalindrome(s)); // true

    s = "A man, a plan, a canal, Panama!";
    System.out.println(s + " -> " + Utils.isPalindrome(s)); // true

    s = "Amor, Roma";
    System.out.println(s + " -> " + Utils.isPalindrome(s)); // true
}

如果是这样，我可以知道为什么维基百科说不可能一次性测试回文吗？我是不是忽略了什么？

Answer 1

问题不在于检查内存中的字符串是否为回文。如果你能把字符串读入内存，检查就很容易完成，但是你已经把字符串读入内存用完了一遍，所以检查是第二遍。

但这只有在整个字符串都适合内存时才有效。由于前提是内存是有限的，这意味着你无法验证长度超过内存容量的字符串是否是回文，这就是你引用的句子所说的。

相比之下，您可以使用有限的内存对任意长的字符串进行大量检查。例如，您可以检查字符串的长度是否可以被 5 整除。您可以检查字符串中的每个 a 是否紧跟一个 b。通常，您可以检查字符串是否与任何正则表达式匹配(这里，我指的是数学意义上的正则表达式，而不是“正则表达式”库识别的模式。)但是由于您无法描述所有回文集使用一个正则表达式，您无法一次性验证任意长的字符串是否为回文，仅使用有限的内存量。