Получив строку s, вернуть самую длинную палиндромную подстроку в s.
Пример 1:
Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer.
Пример 2:
Input: s = "cbbd" Output: "bb"
Ограничения:
1 <= s.length <= 1000sсостоят только из цифр и английских букв.
Java-решение
Два разных решения с двумя разными временными сложностями
O(n³)
Для строки n (где n – размер строки) приведенный ниже код сгенерирует/проверит каждую возможную подстроку и для каждой из этих подстрок проверит, это палиндром, который займет O (n/2) или o (n). Таким образом, для генерации каждой возможной подстроки простая грубая сила потребует O (n²), и, поскольку для каждой подстроки я проверяю, является ли это палиндромом, который будет принимать O (n). Комбинируя оба, мы получаем O (n³)
Код
O(n²)
Вверху я просматриваю все элементы в строке, поэтому O(n) для этого. И в каждом цикле я снова просматриваю всю строку (в худшем случае) для этого еще одного O (n). Комбинируя оба, мы получаем O (n²).
