GitHub
Задачи с собеседований: самый длинный палиндром в строке
Для данной строки вернуть самую длинную палиндромную подстроку.
Для данной строки s вернуть самую длинную палиндромную подстроку. Палиндромная подстрока — это подстрока, являющаяся палиндромом.
Самый длинный палиндром: решение
Решение с применением “грубой силы” состоит в том, чтобы просмотреть каждую подстроку в нашей строке и проверить, является ли она палиндромом или нет.
Количество подстрок растет квадратично с размером входной строки (O(n^2)). Проверка строки на предмет того, является ли она палиндромом, растет линейно.
Следовательно, такое решение займет O(n^3) времени.
Вместо этого мы можем просмотреть каждый символ в нашей строке и предположить, что это середина нашего палиндрома. Затем мы устанавливаем два указателя слева и справа от этого символа и смотрим, какой самый длинный палиндром образуется с центром на этом символе. Нам придется проверять палиндромы как четной, так и нечетной длины.
После того, как мы перебрали всю строку, мы можем вернуть самый длинный палиндром.
Временная сложность O(n^2).
-
Рекламные сети1 месяц назад
Telega.in (Телега. ин) – обзор и отзывы. Маркировка рекламных материалов.
-
Медиа1 месяц назад
Разработка новостного приложения. Часть 4
-
Медиа1 месяц назад
Собеседование по System Design: проектируем клон Авито
-
Разработка4 недели назад
Осваиваем ViewModel в Android: «можно» и «нельзя» — Часть 2