Проверить строку на палиндром за O(n) времени, O(1) памяти
Реализуйте isPalindrome(s), возвращающую true, когда s читается одинаково слева направо и справа налево, игнорируя регистр и любой символ, не являющийся буквой. Требования: O(n) по времени и O(1) дополнительной памяти — идите двумя указателями с обоих концов, не создавайте очищенную копию строки. 'A man, a Plan!' — НЕ палиндром, а 'Madam' и '' — да.
function isPalindrome(s) {
// ваш код здесь
}Допишите реализацию.
Два указателя l = 0 и r = s.length - 1 идут к центру. Пропускайте сторону, чей символ не проходит проверку на букву (например, регуляркой вроде /[a-z]/i), затем сравнивайте через toLowerCase; несовпадение возвращает false. Встреча в центре возвращает true. Это O(n) по времени и O(1) дополнительной памяти — очищенная копия не создаётся.
- ✗Строить очищенную или развёрнутую копию, что стоит O(n) памяти вместо O(1)
- ✗Сравнивать символы без приведения обеих сторон к нижнему регистру
- ✗Забыть пропускать не-буквы с ОБЕИХ сторон перед каждым сравнением
- →Как заодно учитывать цифры как значимые символы?
- →Почему пропуск не-букв внутри цикла сохраняет общую сложность O(n)?
Решение
Два указателя стартуют с краёв и сходятся к центру, пропуская не-буквы.
function isPalindrome(s) {
const isLetter = (c) => /[a-z]/i.test(c);
let l = 0, r = s.length - 1;
while (l < r) {
if (!isLetter(s[l])) { l++; continue; } // пропускаем слева
if (!isLetter(s[r])) { r--; continue; } // пропускаем справа
if (s[l].toLowerCase() !== s[r].toLowerCase()) return false;
l++;
r--;
}
return true;
}Как это работает
Указатели идут с обоих концов к центру. Прежде чем сравнить пару символов, каждый указатель проматывается мимо всего, что не является буквой, — поэтому пунктуация и пробелы не влияют на результат. Сравнение делается с приведением к нижнему регистру, так что регистр игнорируется.
Любое несовпадение сразу возвращает false. Если указатели встретились, строка — палиндром. Каждый символ посещается не более одного раза — O(n) по времени и O(1) по памяти, без очищенной копии. Пустая строка проходит цикл ноль раз и корректно возвращает true.
