The fastest way to determine if a string is a palindrome

Question

I need an algorithm that checks with the highest possible runtime if the string is a palindrome (the string can be a sentence with uppercase or lowercase letters, spaces, etc.). All 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 converted a string to a lowercase letter using a function .toLowerCase(), but I don't know how much it affects runtime.

And also I do not know how to effectively solve the problem with punctuation and spaces between words.

Answer 1

I think you can just check the reverse line , 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

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

... , mu , .

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

Answer 4

, .

, , .. .

On performance, toLowerCase is O (n), and any regular regexp analysis will also be O (n). If you are concerned with this, converting and comparing char to char should be the best option.

Answer 5

In ordinary 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); 

Answer 6

Here is some information about my way to detect a palindrome using Java. Feel free to ask a question :) I hope I can help in some way ....

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