DEV Community

faangmaster
faangmaster

Posted on

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

Задача. Проверить, является ли строка палиндромом. Палиндром — это строка, которая читается одинаково слева направо и справа налево.

Например, abcba — палиндром, Abba — не палиндром (если учитываем регистр букв), abc — не палиндром, a — палиндром, aba — палиндром, TENET — палиндром.

Решение. Эту задачу можно решить при помощи техники, которая называется Two Pointers (Два Указателя).

Справка по Two Pointers.

Обычно, когда мы идем циклом по какой-то структуре данных, мы используем один указатель. Обычно это текущий элемент этой структуры данных. Например:

    for (int i = 0; i < str.length(); i++) {
      char c = str.charAt(i);
      .....
    }
Enter fullscreen mode Exit fullscreen mode

В данном случаем i это единственный указатель.

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

Например:

  1. Первый указатель начинает с начала, а второй с конца и они идут навстречу друг другу (как в задаче на палиндромы или в задаче на поиске пар элементов, сумма, которых равна заданному числу в отсортированном массиве).

  2. Оба указателя начинают с начала, но идут с разной скоростью (Например, в задаче, когда надо найти k-й элемент с конца в односвязном списке).

  3. В рамках одного цикла мы одновременно итерируемся по двум структурам данных. (Например, в задаче, где надо слить два отсортированных массива или списка друг с другом, или в задачах, где надо проанализировать календари совещаний разных людей, чтобы проверить доступность людей в определенное время как в outlook).

Вернемся к данной задаче.

В данной задаче, мы будем использовать вариант, когда надо использовать два указателя, один идет с начала строки, второй с конца. Будем сравнивать символы, на которые указывают эти указатели. Если символы разные, то это не палиндром. Если они одинаковые, то первый индекс увеличим на один, а второй уменьшим. Так будем повторять до тех пор, пока первый индекс меньше второго.

Реализация:

    class Solution {
      public boolean isPalindrome(String str) {
        int left = 0;
        int right = str.length() - 1;
        while (left < right) {
          if (str.charAt(left) != str.charAt(right)) {
            return false;
          }
          left++;
          right--;
        }
        return true; 
      }
    }
Enter fullscreen mode Exit fullscreen mode

Time complexity: O(n), Space Complexity: O(1).

Image of Datadog

Create and maintain end-to-end frontend tests

Learn best practices on creating frontend tests, testing on-premise apps, integrating tests into your CI/CD pipeline, and using Datadog’s testing tunnel.

Download The Guide

Top comments (0)

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up