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

Введение

В этом практическом занятии (лабораторной работе) вы научитесь проверять, является ли строка палиндромом на Java. Мы рассмотрим различные подходы, начиная с основательного метода переворота строки и сравнения ее с исходной.

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

Перевернуть строку и сравнить

На этом этапе мы начнем с создания простой Java-программы для переворота строки и последующего сравнения ее с исходной строкой. Это фундаментальный шаг к пониманию манипуляций со строками в Java и станет основой для проверки, является ли строка палиндромом.

Сначала создадим новый Java-файл. В проводнике файлов слева в WebIDE щелкните правой кнопкой мыши в каталоге ~/project, выберите "New File" и назовите его StringReverse.java.

Теперь откройте файл StringReverse.java в редакторе и добавьте следующий код:

public class StringReverse {

    public static void main(String[] args) {
        String originalString = "hello";
        String reversedString = "";

        // Loop through the original string from end to beginning
        for (int i = originalString.length() - 1; i >= 0; i--) {
            // Append each character to the reversedString
            reversedString += originalString.charAt(i);
        }

        System.out.println("Original string: " + originalString);
        System.out.println("Reversed string: " + reversedString);

        // Compare the original and reversed strings
        if (originalString.equals(reversedString)) {
            System.out.println("The string is the same forwards and backwards.");
        } else {
            System.out.println("The string is NOT the same forwards and backwards.");
        }
    }
}

Разберем этот код:

• String originalString = "hello";: Мы объявляем переменную типа String с именем originalString и присваиваем ей значение "hello".
• String reversedString = "";: Мы объявляем пустую переменную типа String с именем reversedString. Здесь мы будем создавать перевернутую строку.
• for (int i = originalString.length() - 1; i >= 0; i--): Это цикл for, который начинается с последнего символа originalString (индекс length() - 1) и идет до первого символа (индекс 0).
• reversedString += originalString.charAt(i);: Внутри цикла originalString.charAt(i) получает символ по текущему индексу i. Затем мы добавляем этот символ к reversedString.
• System.out.println(...): Эти строки выводят исходную и перевернутую строки в консоль.
• if (originalString.equals(reversedString)): Это оператор if, который сравнивает originalString и reversedString с использованием метода equals(). В Java для сравнения содержимого строк следует использовать метод equals(), а не оператор ==.
• Блоки if и else выводят разные сообщения в зависимости от того, совпадают ли строки.

Сохраните файл StringReverse.java (Ctrl+S или Cmd+S).

Теперь откройте терминал внизу WebIDE. Убедитесь, что вы находитесь в каталоге ~/project. Если нет, введите cd ~/project и нажмите Enter.

Скомпилируйте Java-код с помощью команды javac:

javac StringReverse.java

Если нет ошибок, в каталоге ~/project будет создан файл StringReverse.class.

Наконец, запустите скомпилированную Java-программу с помощью команды java:

java StringReverse

Вы должны увидеть вывод, похожий на следующий:

Original string: hello
Reversed string: olleh
The string is NOT the same forwards and backwards.

В этом случае "hello" не совпадает при чтении вперед и назад, поэтому программа правильно определяет это.

Использование подхода с двумя указателями для проверки палиндрома

На предыдущем этапе мы переворачивали всю строку, чтобы проверить, является ли она палиндромом. Хотя этот метод работает, он требует создания новой строки, что может быть неэффективно для очень длинных строк. Более эффективный подход - использовать технику двух указателей.

Техника двух указателей заключается в использовании двух указателей (переменных, которые хранят индексы позиций), которые начинаются с разных концов строки и двигаются к центру. Мы сравниваем символы в этих указанных позициях. Если они всегда совпадают при движении указателей внутрь, строка является палиндромом. Если мы находим хоть одну несоответствие, строка не является палиндромом.

Создадим новую Java-программу для реализации этого. В проводнике файлов слева создайте новый файл с именем PalindromeChecker.java в каталоге ~/project.

Откройте PalindromeChecker.java и добавьте следующий код:

public class PalindromeChecker {

    public static void main(String[] args) {
        String testString = "madam"; // Let's test with a palindrome
        boolean isPalindrome = checkPalindrome(testString);

        if (isPalindrome) {
            System.out.println("\"" + testString + "\" is a palindrome.");
        } else {
            System.out.println("\"" + testString + "\" is not a palindrome.");
        }

        testString = "racecar"; // Another palindrome
        isPalindrome = checkPalindrome(testString);

        if (isPalindrome) {
            System.out.println("\"" + testString + "\" is a palindrome.");
        } else {
            System.out.println("\"" + testString + "\" is not a palindrome.");
        }

        testString = "hello"; // Not a palindrome
        isPalindrome = checkPalindrome(testString);

        if (isPalindrome) {
            System.out.println("\"" + testString + "\" is a palindrome.");
        } else {
            System.out.println("\"" + testString + "\" is not a palindrome.");
        }
    }

    // Method to check if a string is a palindrome using two pointers
    public static boolean checkPalindrome(String str) {
        // Initialize two pointers
        int left = 0; // Pointer starting from the beginning
        int right = str.length() - 1; // Pointer starting from the end

        // Loop while the left pointer is less than the right pointer
        while (left < right) {
            // Compare characters at the left and right pointers
            if (str.charAt(left) != str.charAt(right)) {
                // If characters don't match, it's not a palindrome
                return false;
            }
            // Move the pointers inwards
            left++;
            right--;
        }

        // If the loop completes without finding any mismatch, it's a palindrome
        return true;
    }
}

Вот что происходит в новом коде:

• Мы создали отдельный метод checkPalindrome, который принимает строку (String) в качестве входных данных и возвращает логическое значение (boolean, true, если строка является палиндромом, и false в противном случае). Это делает наш код более организованным и повторно используемым.
• Внутри checkPalindrome мы инициализируем left равным 0 (индекс первого символа) и right равным str.length() - 1 (индекс последнего символа).
• Цикл while (left < right) продолжается, пока левый указатель находится левее правого указателя.
• if (str.charAt(left) != str.charAt(right)) сравнивает символы в текущих позициях left и right. Если они различны, мы сразу понимаем, что строка не является палиндромом, и возвращаем false.
• Если символы совпадают, мы двигаем указатели внутрь: left++ увеличивает левый указатель, а right-- уменьшает правый указатель.
• Если цикл завершается без возврата false, это означает, что все сравниваемые символы совпали, поэтому строка является палиндромом, и мы возвращаем true.
• В методе main мы вызываем checkPalindrome с разными тестовыми строками и выводим результаты.

Сохраните файл PalindromeChecker.java.

Теперь скомпилируйте и запустите программу в терминале:

javac PalindromeChecker.java
java PalindromeChecker

Вы должны увидеть следующий вывод:

"madam" is a palindrome.
"racecar" is a palindrome.
"hello" is not a palindrome.

Это демонстрирует, как подход с двумя указателями эффективно проверяет строки на палиндромность без переворачивания всей строки.

Игнорирование регистра и небуквенных символов при проверке палиндрома

На предыдущем этапе наш проверятель палиндромов работал для простых строк, таких как "madam" и "racecar". Однако в реальной жизни палиндромы часто игнорируют регистр букв и пунктуацию. Например, "A man, a plan, a canal: Panama" считается палиндромом.

На этом этапе мы усовершенствуем нашу программу PalindromeChecker, чтобы она обрабатывала такие случаи, игнорируя небуквенные символы и воспринимая заглавные и строчные буквы одинаково.

Откройте файл PalindromeChecker.java в редакторе WebIDE. Мы изменим метод checkPalindrome.

Замените существующий метод checkPalindrome на следующую обновленную версию:

    // Method to check if a string is a palindrome using two pointers,
    // ignoring case and non-letter characters
    public static boolean checkPalindrome(String str) {
        // Initialize two pointers
        int left = 0; // Pointer starting from the beginning
        int right = str.length() - 1; // Pointer starting from the end

        // Loop while the left pointer is less than the right pointer
        while (left < right) {
            // Move left pointer past non-letter characters
            while (left < right && !Character.isLetter(str.charAt(left))) {
                left++;
            }

            // Move right pointer past non-letter characters
            while (left < right && !Character.isLetter(str.charAt(right))) {
                right--;
            }

            // If left and right pointers haven't crossed and characters don't match (ignoring case)
            if (left < right && Character.toLowerCase(str.charAt(left)) != Character.toLowerCase(str.charAt(right))) {
                // If characters don't match, it's not a palindrome
                return false;
            }

            // Move the pointers inwards
            left++;
            right--;
        }

        // If the loop completes without finding any mismatch, it's a palindrome
        return true;
    }

Вот какие изменения мы внесли:

• Мы добавили два цикла while внутри основного цикла while (left < right).
• Первый вложенный цикл while (while (left < right && !Character.isLetter(str.charAt(left)))) перемещает указатель left вперед, пока он все еще находится слева от указателя right и символ в позиции left не является буквой (!Character.isLetter(...)).
• Второй вложенный цикл while (while (left < right && !Character.isLetter(str.charAt(right)))) перемещает указатель right назад, пока он все еще находится слева от указателя right и символ в позиции right не является буквой.
• Сравнение if (left < right && Character.toLowerCase(str.charAt(left)) != Character.toLowerCase(str.charAt(right))) теперь включает два важных условия:
  • left < right: Это гарантирует, что мы сравниваем символы только в том случае, если указатели не пересеклись после пропуска небуквенных символов.
  • Character.toLowerCase(...): Это преобразует оба символа в нижний регистр перед сравнением, фактически игнорируя регистр.
• Если символы (после преобразования в нижний регистр) не совпадают, мы возвращаем false.
• Если они совпадают, мы перемещаем оба указателя внутрь (left++, right--), чтобы проверить следующую пару символов.

Теперь изменим метод main, чтобы проверить программу на строке, содержащей пробелы, пунктуацию и смешанный регистр. Замените существующие тестовые случаи в методе main на следующие:

    public static void main(String[] args) {
        String testString = "A man, a plan, a canal: Panama"; // A classic palindrome
        boolean isPalindrome = checkPalindrome(testString);

        if (isPalindrome) {
            System.out.println("\"" + testString + "\" is a palindrome.");
        } else {
            System.out.println("\"" + testString + "\" is not a palindrome.");
        }

        testString = "No 'x' in Nixon"; // Another palindrome
        isPalindrome = checkPalindrome(testString);

        if (isPalindrome) {
            System.out.println("\"" + testString + "\" is a palindrome.");
        } else {
            System.out.println("\"" + testString + "\" is not a palindrome.");
        }

        testString = "hello world"; // Not a palindrome
        isPalindrome = checkPalindrome(testString);

        if (isPalindrome) {
            System.out.println("\"" + testString + "\" is a palindrome.");
        } else {
            System.out.println("\"" + testString + "\" is not a palindrome.");
        }
    }

Сохраните файл PalindromeChecker.java.

Скомпилируйте и запустите обновленную программу в терминале:

javac PalindromeChecker.java
java PalindromeChecker

Теперь вы должны увидеть следующий вывод, правильно определяющий палиндромы даже с небуквенными символами и смешанным регистром:

"A man, a plan, a canal: Panama" is a palindrome.
"No 'x' in Nixon" is a palindrome.
"hello world" is not a palindrome.

Вы успешно усовершенствовали свой проверятель палиндромов для обработки более сложных строк!

Резюме

В этом практическом занятии (лабораторной работе) мы научились проверять, является ли строка палиндромом на Java. Мы начали с реализации метода для переворота строки и сравнения ее с исходной строкой, чтобы определить, является ли она палиндромом. Это включало создание Java-файла, написание кода для обхода строки в обратном порядке и использование метода equals() для сравнения.

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