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

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

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

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

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

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

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

В данном случаем 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; 
      }
    }

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