Задача. Проверить, является ли строка палиндромом. Палиндром — это строка, которая читается одинаково слева направо и справа налево.
Например, abcba — палиндром, Abba — не палиндром (если учитываем регистр букв), abc — не палиндром, a — палиндром, aba — палиндром, TENET — палиндром.
Решение. Эту задачу можно решить при помощи техники, которая называется Two Pointers (Два Указателя).
Справка по Two Pointers.
Обычно, когда мы идем циклом по какой-то структуре данных, мы используем один указатель. Обычно это текущий элемент этой структуры данных. Например:
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
.....
}
В данном случаем i это единственный указатель.
Часто, в алгоритмических задачах на массивы, строки и списки можно использовать одновременно два указателя.
Например:
Первый указатель начинает с начала, а второй с конца и они идут навстречу друг другу (как в задаче на палиндромы или в задаче на поиске пар элементов, сумма, которых равна заданному числу в отсортированном массиве).
Оба указателя начинают с начала, но идут с разной скоростью (Например, в задаче, когда надо найти k-й элемент с конца в односвязном списке).
В рамках одного цикла мы одновременно итерируемся по двум структурам данных. (Например, в задаче, где надо слить два отсортированных массива или списка друг с другом, или в задачах, где надо проанализировать календари совещаний разных людей, чтобы проверить доступность людей в определенное время как в 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).
Top comments (0)