Эффективный способ определить, является ли входная строка палиндромом или нет

Question

Я недавно написал этот короткий метод, чтобы определить, является ли строка палиндромом.Мне было интересно, что я мог сделать, чтобы сделать его более эффективным, конечно же, мне не хватает простых встроенных функций, которые могут ускорить вычисления.

Спасибо всем за помощь!

boolean checkPalindrome(String inputString) {

    ArrayList<Character> arrFront = new ArrayList<Character>();
    ArrayList<Character> arrBack = new ArrayList<Character>();

    for(int i=0; i<inputString.length()-1; i++) {
        arrFront.add(inputString.charAt(i));
    }

    for(int i=inputString.length()-1; i>0; i--) {
        arrBack.add(inputString.charAt(i));
    }

    StringBuilder builder1 = new StringBuilder(arrFront.size());
    for (Character c : arrFront) {
        builder1.append(c);
    }
    String front = builder1.toString();

    StringBuilder builder2 = new StringBuilder(arrBack.size());
    for (Character c : arrBack) {
        builder2.append(c);
    }
    String back = builder2.toString();

    return(front.equals(back));
}

Answer 1

Я думаю, что самый простой способ - использовать значение по умолчанию StringBuilder.
Этот класс получил хорошую функцию, которая может быть полезной.Это называется reverse().Он делает то, что говорит, он переворачивает строку, которая разбирается в StringBuilder.При этом довольно просто проверить, равна ли данная строка обращенной.

Например, вы можете сделать:

public boolean isPallindrome(String input){
    StringBuilder reversed = new StringBuilder(input);
    reversed.reverse();
    /*
     * Just replace equals with equalsIgnoreCase
     * to ignore the case
     */
    return(reversed.toString().equalsIgnoreCase(input));
}

Данный код просто создает экземпляр StringBuilder и напрямуюдобавляет вход.Затем он переворачивает StringBuilder и проверяет, равняется ли ввод перевернутой строке.

Answer 2

может относиться к статье @FernandoPelliccioni Проверить строку для палиндрома .Он сделал очень тщательный анализ для этого решения.

для простого решения:

public static boolean isPalindrome(String str) {
    return str.equals(new StringBuilder(str).reverse().toString());
}

с точки зрения эффективности:

public static boolean isPalindrome(String str) {
    int n = str.length();
    for (int i = 0; i < n/2; ++i) {
       if (str.charAt(i) != str.charAt(n-i-1)) return false;
    }
    return true; 
}

Answer 3

Вот более простой способ.

public boolean checkPalindrome(String str) {
    int len = inputString.length()/2;
    for(int i = 0 ; i < len ; i++) {
        if(str.charAt(i) != str.charAt(str.length()-1-i)) {
            return false;
        }
    }
    return true;
}

Когда длина строки равна N.Сложность времени составляет O(N/2).Примечание: вам не нужно проверять средний символ, если длина строки нечетна, потому что она сама по себе.

Например,

В ssstsss, вам не нужнопроверьте t.

А так как len является int.Это не может выразить decimal part.Это автоматически падает.len из ssstsss равно 3, поскольку оно равно 7/2 = 3.5 и падает 0.5.

Даже если его длина равна, он будет работать.Например, abccba.Длина составляет 6.И len - это 3.Если длина чётного числа, вы должны проверить даже два символа в середине, которые равны cc.

Answer 4

С точки зрения эффективности, это не всегда встроенные функции и использование библиотек (хотя во многих случаях они являются лучшим выбором).Но иногда такой простой цикл может быть самым простым и эффективным способом:

private boolean checkPalindrome(String inputString) {
    for(int i = 0, j = inputString.length() - 1; i < j; i++, j--) {
        if(inputString.charAt(i) != inputString.charAt(j)) {
            return false;
        }
    }
    return true;
}