Друзья, давайте поговорим про палиндромы.
Палиндром — это строка, которая читается одинаково как справа налево, так и слева направо.
На языке Python можно написать достаточно короткий код, определяющий, является ли строка палиндромом. Достаточно сравнить текущую строку с перевернутой строкой, а делается это очень легко с помощью срезов.
Но такое решение нельзя назвать хорошим, поскольку оно дополнительно создает копию строки. Если начальная строка будет достаточно большой, это может привести к серьезной нагрузке на систему.
Классическим решением задачи определения палиндрома является метод двух указателей(мы сейчас как раз пишем о нем модуль в новом курсе по алгоритмам) .
Алгоритм решения: заводим два указателя
Такое решение быстрее, а самое главное, оно не требует дополнительной памяти.
Сталкивались ли вы с задачами, в которых нужно применить метод двух указателей? Они ну очень часто встречаются на алгоритмической части собеседований.
#полезныйматериал #алгоритм #палиндром
Палиндром — это строка, которая читается одинаково как справа налево, так и слева направо.
На языке Python можно написать достаточно короткий код, определяющий, является ли строка палиндромом. Достаточно сравнить текущую строку с перевернутой строкой, а делается это очень легко с помощью срезов.
Но такое решение нельзя назвать хорошим, поскольку оно дополнительно создает копию строки. Если начальная строка будет достаточно большой, это может привести к серьезной нагрузке на систему.
Классическим решением задачи определения палиндрома является метод двух указателей
Алгоритм решения: заводим два указателя
left и right — индексы первого и последнего символа строки. В цикле пока left < right сравниваем соответствующие указателям left и right символы исходной строки и в зависимости от того, равны они или нет, двигаемся дальше (left += 1, right -= 1) или завершаем алгоритм.Такое решение быстрее, а самое главное, оно не требует дополнительной памяти.
Сталкивались ли вы с задачами, в которых нужно применить метод двух указателей? Они ну очень часто встречаются на алгоритмической части собеседований.
#полезныйматериал #алгоритм #палиндром