Проверка на палиндромы в Java

Введение

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

Skills Graph

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

Первым методом, который мы реализуем, будет подход с двумя указателями. Мы создадим метод isPalindrome, который принимает строку в качестве входных данных и возвращает логическое значение, указывающее, является ли строка палиндромом или нет.

public class PalindromeChecker {
    public static boolean isPalindrome(String str) {
        int start = 0;
        int end = str.length() - 1;

        while (start < end) {
            char startChar = Character.toLowerCase(str.charAt(start));
            char endChar = Character.toLowerCase(str.charAt(end));

            if (startChar!= endChar) {
                return false;
            }

            start++;
            end--;
        }

        return true;
    }
}

Метод isPalindrome использует два указателя, start и end, которые начинаются соответственно с начала и конца строки. Цикл продолжается до тех пор, пока два указателя не встретятся посередине.

На каждой итерации мы сравниваем символы, находящиеся по указателям start и end. Если они не равны, мы возвращаем false. Если они равны, мы обновляем указатели, чтобы проверить следующую пару символов в строке.

Для тестирования нашего метода мы можем добавить метод main и вызвать метод isPalindrome с различными входными строками.

public class PalindromeChecker {
    public static boolean isPalindrome(String str) {
        // Реализация метода isPalindrome
    }

    public static void main(String[] args) {
        System.out.println("Is 'racecar' a palindrome? " + isPalindrome("racecar"));
        System.out.println("Is 'hello' a palindrome? " + isPalindrome("hello"));
    }
}

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

Следующим методом, который мы реализуем, будет рекурсивный подход. Мы создадим новый метод isPalindromeRecursive, который принимает строку, начальный индекс и конечный индекс в качестве входных данных.

public class PalindromeChecker {
    public static boolean isPalindrome(String str) {
        String lowercaseStr = str.toLowerCase();
        return isPalindromeRecursive(lowercaseStr, 0, lowercaseStr.length() - 1);
    }

    public static boolean isPalindromeRecursive(String str, int start, int end) {
        if(start >= end) {
            return true;
        }

        char startChar = Character.toLowerCase(str.charAt(start));
        char endChar = Character.toLowerCase(str.charAt(end));

        if(startChar!= endChar) {
            return false;
        }

        return isPalindromeRecursive(str, start + 1, end - 1);
    }

    public static void main(String[] args) {
        // Тесты для методов isPalindrome и isPalindromeRecursive
    }
}

Метод isPalindromeRecursive использует рекурсию для проверки, является ли строка палиндромом или нет. У нас есть два базовых случая:

1. Если начальный индекс start больше или равен конечному индексу end, это означает, что мы проверили все символы в строке и они совпадают, поэтому мы возвращаем true.
2. Если символы по начальному и конечному индексам не равны, мы возвращаем false.

Если ни один из базовых случаев не выполняется, мы снова вызываем isPalindromeRecursive с обновленными индексами.

Теперь мы можем протестировать наш рекурсивный метод, вызвав его внутри метода main.

public class PalindromeChecker {
    public static boolean isPalindrome(String str) {
        // Реализация метода isPalindrome
    }

    public static boolean isPalindromeRecursive(String str, int start, int end) {
        // Реализация метода isPalindromeRecursive
    }

    public static void main(String[] args) {
        System.out.println("Is 'racecar' a palindrome? " + isPalindromeRecursive("racecar", 0, 6));
        System.out.println("Is 'hello' a palindrome? " + isPalindromeRecursive("hello", 0, 4));
    }
}

Переворачивание строки для проверки на палиндромы

Последним методом, который мы реализуем, является метод переворачивания строки. Мы создадим новый метод isPalindromeReverse, который принимает строку в качестве входных данных.

public class PalindromeChecker {
    public static boolean isPalindrome(String str) {
        // Реализация метода isPalindrome
    }

    public static boolean isPalindromeRecursive(String str, int start, int end) {
        // Реализация метода isPalindromeRecursive
    }

    public static boolean isPalindromeReverse(String str) {
        String reversed = "";

        for (int i = str.length() - 1; i >= 0; i--) {
            reversed += str.charAt(i);
        }

        return str.equalsIgnoreCase(reversed);
    }

    public static void main(String[] args) {
        // Тесты для методов isPalindrome и isPalindromeRecursive
        System.out.println("Is 'racecar' a palindrome? " + isPalindromeReverse("racecar"));
        System.out.println("Is 'hello' a palindrome? " + isPalindromeReverse("hello"));
    }
}

Метод isPalindromeReverse создает новую строку reversed и заполняет ее путем итерации по входной строке с конца до начала. Затем мы возвращаем true, если две строки равны, игнорируя регистр.

Мы можем протестировать метод, добавив вызов isPalindromeReverse в метод main.

Использование Java Streams для проверки на палиндромы

Наконец, мы будем использовать API Java Streams для проверки на палиндромы. Мы создадим новый метод isPalindromeStream, который принимает строку в качестве входных данных.

import java.util.stream.IntStream;

public class PalindromeChecker {
    public static boolean isPalindrome(String str) {
        // Реализация метода isPalindrome
    }

    public static boolean isPalindromeRecursive(String str, int start, int end) {
        // Реализация метода isPalindromeRecursive
    }

    public static boolean isPalindromeReverse(String str) {
        // Реализация метода isPalindromeReverse
    }

    public static boolean isPalindromeStream(String str) {
        String lowercaseStr = str.toLowerCase();

        return IntStream.range(0, lowercaseStr.length() / 2)
              .noneMatch(i -> lowercaseStr.charAt(i)!= lowercaseStr.charAt(lowercaseStr.length() - i - 1));
    }

    public static void main(String[] args) {
        // Тесты для методов isPalindrome и isPalindromeRecursive
        System.out.println("Is 'racecar' a palindrome? " + isPalindromeStream("racecar"));
        System.out.println("Is 'hello' a palindrome? " + isPalindromeStream("hello"));
    }
}

Метод isPalindromeStream использует класс IntStream для генерации диапазона индексов, которые мы можем использовать для сравнения символов в строке.

Мы используем метод noneMatch, чтобы вернуть true, если ни один из символов не нарушает условие, что ith и n-i-1th символы равны, где n - длина строки, а i - индекс.

Мы можем протестировать метод, добавив вызов isPalindromeStream в метод main.

Обзор

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

1. Двух-указатель подход
2. Рекурсивный подход
3. Подход с переворачиванием строки
4. Подход с использованием Java Streams

Теперь, когда вы понимаете эти методы, вы можете использовать их для решения более сложных задач!