Функция определения палиндрома

Однажды мне пришлось решать задачу определения палиндрома. Так как вопрос был задан в лоб и времени было мало, решение было простецким:

function pal (str) {
    str = str.toLowerCase().replace(/ /g, '');

    return str.split('').reverse().join('') == str;
}

Тут всё просто: приводим строку к нижнему регистру, убираем пробелы, разбиваем на массив, меняем порядок следования элементов, собираем новый массив в строку и сравниваем с исходной строкой.

Что бы убрать возможные знаки препинания из исходной строки, которые бы могли помешать работе, надо изменить регулярку:

// спасибо Тимур
str = str.toLowerCase().replace(/[^a-zA-Zа-яА-Я]/g, '');

Вот собственно и всё. Способ крайне прост и понятен, но мы пять раз проходим по всему набору символов. А если строка из миллиона символов?

В этом случае лучшим решением будет пожертвование простотой в угоду скорости:

function pal (str) {
    // нормализуем строку
    str = str.toLowerCase().replace(/[^a-zA-Zа-яА-Я]/g, ''); 
    
    var strLen = str.length; // сохраняем значение её длины
    
    // берём половину длины строки и округляем до большего
    for (var i = 0, l = Math.ceil(strLen / 2); i < l; i += 1) { 
        // тут самое интересное: мы берём первый символ 
        // строки и сравниваем его с последним. 
        // Второй с предпоследним и так далее.
        // если крайние символы не совпадают, прерываем цикл. 
        // Ясно, что уже не палидром.
        if (str.charAt(i) !== str.charAt(strLen-(1+i))) { 
            console.log('Не палиндром!');
            return false;
        }
    }
    // если все символы из первой половины строки совпадают 
    // с аналогичными символами из второй, 
    // значит исходная строка - палиндром.
    console.log('Палиндром')
}

Видно, что во втором примере полный обход строки осуществляется лишь дважды. А при первом же несовпадении цикл прерывается, не расходуя ресурсы понапрасну.

На практике такого рода оптимизация не имеет смысла и даёт выигрыш всего в 10 мс. при длине строки в 1 000 000 символов :)

UPD: Мда, интернет пестрит вариантами определения палиндрома и мои изыскания отнюдь не пионерские.