Самый быстрый способ определения, является ли строка палиндром

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() функцию, но я не знаю, насколько это влияет на время выполнения.

А также я не знаю, как эффективно решить проблему с пунктуацией и пробелами между словами.

Answer 1

Я думаю, вы можете просто проверить строку обратный, не?

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

Answer 2

Ваше решение кажется очень хорошо, когда речь идет об эффективности.

Что касается второго вопроса, то вы можете просто удалить все пробелы и точки и т.д., прежде чем начать тестирование:

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 3

Эффективное не то же самое в эффективной.

Ваш ответ эффективен, если вы рассматриваете пробелы, специальные символы и т. Д. Даже акценты могут быть проблематичными.

Об эффективности, toLowerCase - это O (n), и любое разбор регулярного выражения будет также O (n). Если вы касаетесь этого, конвертировать и сравнивать char по char должен быть лучшим вариантом.

Answer 4

В нормальных случаях:

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

Answer 5

Это исключает любое копирование. Функции 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; 

Попробуйте бенчмарка это ... Я надеюсь, что решение мю может быть самым быстрым, но без измерения вы никогда не знаете.

Answer 6

Вот некоторые сведения о моем способе обнаружения палиндрома с использованием 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())); 
    } 
}