ЯжПрограммист.com

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

Решение должно работать по скорости за O(N), где N — длина строки на входе, и O(1) по памяти.

Формат ввода
В единственной строке записана фраза или слово. Буквы могут быть только латинские. Длина текста не превосходит 20000 символов. Фраза может состоять из строчных и прописных латинских букв, цифр, знаков препинания.
Выведите «True», если фраза является палиндромом, и «False», если не является.

Это задача 125 на leetcode и есть похожая немного усложненная на яндекс coderun 193.

Пример 1
Ввод: A man, a plan, a canal: Panama
Вывод: true

Пример 2
Ввод: AbaCdaba
Вывод: false

Разбор решения:

Будем решать эту задачу методом 2-х указателей, одним пойдем с начала строки к концу, а вторым с конца к началу. Будем проверять каждый символ каждого указателя на равенство.
По условию символы кроме цифр и символов не из латинского алфавита не должны участвовать в сравнении, поэтому при попадании указателя на них будем сдвигать указатель до тех пор, пока не появится допускаемый символ.
По условию выхода, может быть 2 варианта - либо наши указатели встретятся на соседних символах, либо на одном и том же. Если до этого момента мы не встретили различающихся символов, выводим - true, как только встретили отличающиеся, выводим - false.

Решение(Java):


public class Solution {
 private boolean isAscii(char c) {
    return (c >= '0' && c <= '9') || (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z');
  }

  public boolean isPalindrome(String s) {
    int i = 0, i2 = s.length() - 1;
    while (true) {
      if (i >= i2) {
        return true;
      }
      if (!isAscii(s.charAt(i))) {
        i++;
        continue;
      }
      if (!isAscii(s.charAt(i2))) {
        i2--;
        continue;
      }
      if (i >= i2) {
        return true;
      }
      if (Character.toLowerCase(s.charAt(i++)) != Character.toLowerCase(s.charAt(i2--))) {
        return false;
      }
    }
  }
}