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

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

Например, 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).