Является ли строка палиндромом Java

Question

Нужно объявить некоторую строковую переменную в программе, проверить, что данная строка является палиндромом – то есть читается одинаково слева направо и справа налево. При проверке не учитывать регистр символов и учитывать ТОЛЬКО буквы. Примеры палиндромов: «Аргентина манит негра», «Madam'...........bbI'm Adam», «Я - арка края». Сделать это всё нужно без создания новой строки и без удаления символов из строки.

Ниже мой код, который в некоторых случаях работает неправильно. Возможно нужно сделать так, чтобы после проверки левого символа, правый символ тоже ВСЕГДА проверялся или поменять само условие цикла (но это не точно).

import java.util.Scanner;

public class Palindrome {
    public static boolean isPalindrome(String line) {
        if (line.isEmpty()) {
            return true;
        }

        line = line.toUpperCase();

        int i = 0;
        int j = 0;

        while (i < line.length() / 2) {
            char leftSymbol = line.charAt(i);
            char rightSymbol = line.charAt(line.length() - j - 1);

            if (!Character.isLetter(leftSymbol)) {
                j--;
            } else if (!Character.isLetter(rightSymbol)) {
                i--;
            } else if (leftSymbol != rightSymbol) {
                return false;
            }

            i++;
            j++;
        }

        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("Введите строку на проверку:");
        String line = scanner.nextLine();

        System.out.println(isPalindrome(line));
    }
}

Answer 1

Много всяких непоняток у вас в коде, потому я просто переписал основную часть.

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

Код проверье на корректность сами.

public static boolean isPalindrome(String line) {
    if (line.isEmpty()) {
        return true;
    }
    
    int left = 0;
    int right = line.length() - 1;

    while (left < right) {
        char leftSymbol = Character.toLowerCase(line.charAt(left));
        char rightSymbol = Character.toLowerCase(line.charAt(right));

        if (!Character.isLetter(leftSymbol)) {
            left ++;
        } else if (!Character.isLetter(rightSymbol)) {
            right--;
        } else if (leftSymbol != rightSymbol) {
            return false;
        }
        else {
            left ++;
            right--;
        }
    }
    return true;
}

Answer 2

Недостатки

Строка line = line.toUpperCase(); нарушает требование не копировать строку.
Условие цикла while (i < line.length() / 2) { хорошо работает пока в строке одни буквы. Но в примере "__ab" ваш код найдёт палиндром, потому что цикл завершиться до того как индекс i дойдёт до действительных букв.
Не обработаны суррогатные пары.
Сложные манипуляции с индексами: инкремент потом декремент. Сложные, но правильные.
Сравнения верхних регистров символов не достаточно для сравнения без учёта регистра (взято из ответа Nowhere Man).

Исправление

В документации по String.equalsIgnoreCase описан алгоритм сравнения без учёта регистра: сравнить сами символы, сравнить их верхние регистры, сравнить их нижние регистры. Если хотя бы одно сравнение успешно, символы равны. Вот код:

    public static boolean equalsIgnoreCase(int c1, int c2) {
        return 
                                  c1  ==                       c2  ||
            Character.toUpperCase(c1) == Character.toUpperCase(c2) ||
            Character.toLowerCase(c1) == Character.toLowerCase(c2)
        ;
    }

Пусть индекс j движется от конца строки к началу. Цикл будем останавливать когда порядок индексов i и j изменится. Копирование строки убрано. Символы заменены на "кодовые точки" для обработки суррогатных пар. Сложность работы с индексами осталась на месте. Первоначальная проверка на пустую строку убрана:

    public static boolean isPalindrome(String line) {
        int i = 0;
        int j = line.length() - 1;

        while (i < j) {
            int ci = line.codePointAt(i);
            int cj = line.codePointAt(j);

            if (!Character.isLetter(ci)) {
                j++;
            } else if (!Character.isLetter(cj)) {
                i--;
            } else if (!equalsIgnoreCase(ci, cj)) {
                return false;
            }

            i++;
            j--;
        }

        return true;
    }

Пытаемся избежать множественных инкрементов/декрементов индексов:

    public static boolean isPalindrome(String line) {
        int i = 0;
        int j = line.length() - 1;

        while (i < j) {
            int ci = line.codePointAt(i);
            if (!Character.isLetter(ci)) {
                i++;
                continue;
            }

            int cj = line.codePointAt(j);
            if (!Character.isLetter(cj)) {
                j--;
                continue;
            }

            if (equalsIgnoreCase(ci, cj)) {
                i++;
                j--;
                continue;
            }

            return false;
        }

        return true;
    }

Ещё один вариант: ищем букву слева и букву справа, сравниваем если найдены. Три вложенных цикла. Кому-то легче разобраться в такой логике:

    public static boolean isPalindrome(String line) {
        int i = -1;
        int j = line.length();

        int ci = ' ';
        int cj = ' ';
        while (i < j) {
            if (!equalsIgnoreCase(ci, cj)) {
                return false;
            }

            // поиск следующей буквы
            for (++i; i < j; ++i) {
                ci = line.codePointAt(i);
                if (Character.isLetter(ci)) {
                    break;
                }
            }

            // поиск предыдущей буквы
            for (--j; i < j; --j) {
                cj = line.codePointAt(j);
                if (Character.isLetter(cj)) {
                    break;
                }
            }
        }

        return true;
    }

Answer 3

Предыдущие ответы (особенно ответ Станислава Володарского) решают почти все проблемы представленного кода, при условии ограниченного набора алфавитов / языков, для которых выполняется проверка слов на палиндромность.

К примеру, корректное сравнение без учёта регистра следует выполнять для строк при помощи метода String::equalsIgnoreCase, а не путём приведения символов / кодовых точек к единому регистру. Это позволит правильно обрабатывать турецкие пары символов "Iı", "İi".

Также для алфавитов, в которых часто используются диакритические знаки (немецкий, французский и др.) может понадобиться нормализация строки (например, при помощи класса java.text.Normalizer) с последующим удалением диакритических знаков. К тому же это позволит преобразовать некоторые лигатуры типа ﬃ (но не буквы типа Æ, æ, немецкий эсцет ß), для обработки которых потребуется соответствующий "костыль".

Вариант решения с учётом вышесказанного:

private static String removeAccents(String line) {
    return Normalizer.normalize(line, Normalizer.Form.NFKD).replaceAll("\\p{M}", "");
}

private static String fixLigatures(String line) {
    return line.replaceAll("(?ui)Æ", "ae")
        .replaceAll("(?ui)Œ", "oe")
        .replaceAll("(?ui)ß", "ss");  // и т.д. по мере необходимости
}

public static boolean isPalindrome(String line) {
    if (line.isEmpty()) {
        return true;
    }

    line = removeAccents(fixLigatures(line));

    for (int i = 0, j = line.length() - 1; i < j; i++, j--) {
        // ищем крайнюю букву слева
        while (i < j && !Character.isLetter(line.codePointAt(i))) i++;
        // ищем крайнюю букву справа
        while (i < j && !Character.isLetter(line.codePointAt(j))) j--;

        String left = line.substring(i, i + 1);
        String right = line.substring(j, j + 1);
        if (!left.equalsIgnoreCase(right)) {
            return false;
        }
    }

    return true;
}

Результаты тестов:

Введите строки на проверку:
'' palindrome? true
'a' palindrome? true
'Aa' palindrome? true
'aXa' palindrome? true
'IvI idi Ix: İ...F i - xı! IDi IVi' palindrome? true
'içi' palindrome? true
'rêver' palindrome? true
'sémèmes' palindrome? true
'ﬃ ﬁ ifi ﬀ' palindrome? true
'Straße essarts' palindrome? true
'Ææa' palindrome? true
'Пустите, летит суп!' palindrome? true

БЛОГ НА HUSL

Является ли строка палиндромом Java

Ответы (3 шт):

Недостатки

Исправление