Valid palindrome (opens in a new tab)

var isPalindrome = function(s) {
    let cleanStr = s.replace(/\W/g, '').toLowerCase();
    let p = 0;
    let p2 = cleanStr.length - 1;
 
    while(p < p2) {
        if (cleanStr[p] !== cleanStr[p2]) {
            return false
        }
        p++;
        p2--;
    }
 
    return true;
};

1. Регулярное выражение [^a-z0-9] используется для поиска всех символов, которые не являются ни буквами английского алфавита (нижний или верхний регистр), ни числами. Получившаяся строка затем приводится к нижнему регистру чтобы обеспечить регистронезависимое сравнение символов.
2. Устанавливаются два указателя: один (p) в начале очищенной строки, второй (p2) в конце.
3. Затем, пока указатели не встретятся прямо посредине строки, мы сравниваем символы, на которые указывают p и p2.
4. Если символы равны, мы продолжаем движение вперед / назад и сравниваем следующую пару символов.
5. Если символы не равны, возвращаем false - это значит, что строка не является палиндромом.
6. Если все пары символов совпадают и p и p2 встречаются посредине, возвращаем true - это значит, что строка является палиндромом.

Алгоритмическая сложность:

Сложность алгоритма составляет O(n), где n - это длина входной строки s.

Временная сложность:

1. Приведение к нижнему регистру и замена недопустимых символов (O(n)): Это зависит от длины входной строки, поскольку ее каждый символ просматривается и заменяется по необходимости.
2. Обход строки (O(n)): Подобно первому шагу, этот зависит от длины строки, поскольку мы проходим по половине символов строки.

Таким образом, общая временная сложность составляет O(n) + O(n) = O(n).

Пространственная сложность:

1. Память для cleanStr (O(n)): Нам требуется дополнительное пространство для хранения очищенной строки.

Таким образом, пространственная сложность составляет O(n).

В целом, алгоритм является эффективным, так как он выполняет только один проход по входной строке, минимизируя использование дополнительной памяти.