Проверяет понимание оценки временной и пространственной сложности алгоритма проверки строки на палиндром.
Палиндром — это строка, которая читается одинаково слева направо и справа налево, например, 'racecar' или 'level'. Простейший способ проверки — сравнить символы с обоих концов, двигаясь к центру. Этот подход позволяет оценить сложность алгоритма.
Алгоритм с двумя указателями (левый и правый) проходит по строке, сравнивая пары символов. В худшем случае мы делаем n/2 сравнений, где n — длина строки. Поэтому временная сложность — O(n), так как константа 1/2 не влияет на асимптотику.
Если мы используем только два указателя и не создаем дополнительных структур, пространственная сложность — O(1). Однако если мы создаем перевернутую копию строки (например, через reverse), то потребуется O(n) дополнительной памяти.
function isPalindrome(s) {
let left = 0;
let right = s.length - 1;
while (left < right) {
if (s[left] !== s[right]) return false;
left++;
right--;
}
return true;
}
// Время: O(n), память: O(1)Оптимальный алгоритм проверки палиндрома использует два указателя и имеет линейную временную сложность O(n) и константную пространственную O(1). Это важно для обработки длинных строк, так как алгоритм масштабируется линейно и не требует лишней памяти.
