The fastest method of determining if a string is a palindrome

Question

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 :

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 .

And as well I don't know how to solve the problem with punctuation and spaces between words in a effective way.

Answer 1

I think you can just check for string reverse, not?

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

Or, for versions earlier than JDK 1.5:

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

Answer 2

This avoids any copying. The functions isBlank and toLowerCase are rather unspecified in your question, so define them the way you want. Just an example:

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.

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.