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

Question

我遇到了"回文"的概念.我试着通过阅读维基百科来理解

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

该段引起了我的注意

这意味着具有有限内存量的计算机不可能一次性可靠地测试回文.

我想测试一个给定的字符串是否是"回文"是非常直接的？我出了一个快速的代码.

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.通常,您可以检查字符串是否与任何正则表达式匹配(这里,我的意思是数学意义上的正则表达式,而不是"正则表达式"库识别的模式.)但是因为您无法使用正则表达式来描述所有回文的集合一个正则表达式,你不能在一次传递中验证一个任意长的字符串是一个回文,只使用有限的内存.