Статьи
Утилиты Telegram YouTube Отзывы

Алгоритм определения палиндрома

Видеогайд

8 июля 2022

Тэги: Java, алгоритмы, головоломки.

Содержание

  1. Что такое палиндром
  2. Проверка слова
  3. Проверка фразы

Давайте реализуем алгоритм поиска слов-палиндромов на Java.

Что такое палиндром

Для начала надо определиться, что же такое палиндром? Палиндром – это слово или строка текста, которая читается слева направо и справа налево одинаково. Например, палиндромами являются такие слова как «ага», «дед», «довод», «кабак», «мадам», «шалаш». В более широком смысле число «101» также является палиндромом.

Проверка слова

Давайте сначала рассмотрим более простой алгоритм, который на вход получает одно слово без пробелов. В случае, если данное слово палиндром – возвращаем true.

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

private boolean isWordPalindrome(String word) {
    var chars = word.toCharArray();
    var left = 0; // индекс первого символа
    var right = chars.length - 1; // индекс последнего символа
    while (left < right) { // пока не дошли до середины слова
        if (chars[left] != chars[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

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

Затем заводим две переменных left и right для хранения левого и правого индекса соответственно.

После этого в цикле сравниваем левый и правый символы между собой до тех пор, пока левый индекс меньше правого. Если они окажутся равными или левый будет больше правого – они пересеклись.

В самом цикле проверяем равенство левого и правого символа. Если они различны – сразу возвращаем false и выходим из метода. Далее левый символ увеличиваем на 1, а правый – уменьшаем на 1.

Если мы дошли до середины строки и ни разу не встретили различий, то возвращаем true.

Проверка фразы

Теперь усложним задачу и будем проверять не отдельное слово, а целую фразу. Приведу несколько фраз-палиндромов. Попробуйте прочитать их справа налево.

  • Искать такси
  • Лидер бредил
  • А роза упала на лапу Азора
  • Уж редко рукою окурок держу

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

Взяв за основу ранее рассмотренный метод, немного модифицируем его, преобразуя сначала все символы в нижний регистр:

private boolean isTextPalindrome(String text) {
    var chars = text.toLowerCase().toCharArray();
    var left = 0;
    var right = chars.length - 1;
    while (left < right) {
        if (chars[left] != chars[right]) {
            return false;
        }
        // ...

Теперь нам нужно не просто единожды инкрементировать левый индекс, а увеличивать его до тех пор, пока он меньше правого индекса и пока левый символ будет пробелом. Для этого используем цикл с пост-условием do-while:

do {
    left++;
} while (left < right && chars[left] == ' ');

Аналогично правый индекс уменьшаем до тех пор, пока он больше левого и пока правый символ – пробел:

do {
    right--;
} while (right > left && chars[right] == ' ');

В итоге наш улучшенный метод примет следующий вид:

private boolean isTextPalindrome(String text) {
    var chars = text.toLowerCase().toCharArray();
    var left = 0;
    var right = chars.length - 1;
    while (left < right) {
        if (chars[left] != chars[right]) {
            return false;
        }

        do {
            left++;
        } while (left < right && chars[left] == ' ');

        do {
            right--;
        } while (right > left && chars[right] == ' ');
    }
    return true;
}

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

Реализацию данного алгоритма у вас могут спросить на собеседовании, поэтому его полезно знать.


Облако тэгов

Kotlin, Java, Spring, Spring Boot, Spring Data, SQL, PostgreSQL, Oracle, Linux, Hibernate, Collections, Stream API, многопоточность, файлы, Nginx, Apache, maven, gradle, JUnit, YouTube, новости, руководство, ООП, алгоритмы, головоломки, rest, GraphQL, Excel, XML, json, yaml.

Последние статьи

Комментарии

Добавить комментарий

×

devmark.ru