[Алгоритмическое упражнение 02] 5. Самая длинная палиндромная подстрока — скользящее окно

алгоритм LeetCode
[Алгоритмическое упражнение 02] 5. Самая длинная палиндромная подстрока — скользящее окно

Мало знаний, большой вызов! Эта статья участвует в "Необходимые знания для программистов«Творческая деятельность

Эта статья участвовала в "Проект «Звезда раскопок»”, чтобы выиграть творческий подарочный пакет и бросить вызов творческим поощрительным деньгам.

⭐Эта статья включена вgithub-JavaExpert, путь развития технических экспертов, включая полный маршрут изучения Java и вспомогательные учебные материалы, добро пожаловать звездочка ⭐

Палиндром означает, что правильный ум такой же, как и отсталый ум, например: Шанхайская водопроводная вода берется из моря.

—— Горячий комментарий Leetcode по этому вопросу

В двустишии есть палиндром "Вода из-под крана в Шанхае берется из моря", у вас есть следующий куплет?

iShot2021-10-13 11.38.07.png

предисловие

Всем привет, я а.

Запутанный алгоритм, редко запутанный

Сегодня давайте возьмем средний вопрос, посмотрим, сколько у вас навыков?

Question

5. Самая длинная палиндромная подстрока

Сложность: умеренная

Для заданной строки s найти самую длинную подстроку палиндрома в s.

Пример 1:

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

Пример 2:

输入：s = "cbbd"
输出："bb"

Пример 3:

输入：s = "a"
输出："a"

Пример 4:

输入：s = "ac"
输出："a"

намекать:

1

Solution

Мы сделали вопрос раньше:самая длинная уникальная подстрока. использовал滑动窗口法.

Этот вопрос увеличивает ограничения палиндрома, поэтому, как быть с палиндромом, вы можете написать палиндром на бумаге, чтобы наблюдать, каковы характеристики?

Расхождение от центральной точки к обоим концам

Правильно, поэтому нам нужно сдвинуть эту центральную точку и расширить влево и вправо для каждой центральной точки, чтобы определить, равны ли левый и правый символы.

  • ПучокnullИ особые обстоятельства, чтобы избавиться от пустой строки
  • Есть скользящее и изменяемое по размеру окно, левый край окна (начало) не двигается, а правый конец (конец) смещается назад
  • Поскольку существует два типа длины строки, нечетная и четная, нам нужно вычислить расширение из одного символа и расширение между двумя символами одновременно.
  • Найдите относительно длинное из двух расширений как текущий максимум
  • новыйstartС чего начать, как расширить строку — это просто вопрос рассмотрения

Есть еще одноАлгоритм повозки, запряженной лошадьмиЭто быстрее, но имеет определенную степень сложности. Интервью обычно не появляются. Заинтересованные студенты могут посмотреть

Code

всеleetcodeкод был синхронизирован сgithub

Добро пожаловатьstar

/**
 * @author 一条coding
 */
class Solution {
    public String longestPalindrome(String s) {
    if (s == null || s.length() < 1) return "";
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCenter(s, i, i);
        int len2 = expandAroundCenter(s, i, i + 1);
        int len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}

private int expandAroundCenter(String s, int left, int right) {
    int L = left, R = right;
    while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
        L--;
        R++;
    }
    return R - L - 1;
}

Result

Анализ сложности

  • Временная сложность: O(N)

image-20210802132533270

Last

Тяжело идти одному, тяжело плакать одномуВедь силы человека ограничены, и путь человека обречен быть одиноким. Когда вы составили план и готовы с энтузиазмом отправиться в путь, вы должны найти партнера.Подобно танскому монаху, изучающему священные писания с Запада, четыре мастера и ученика объединяются, чтобы преодолеть девять-девять-восемь. -одни трудности. Так что, пожалуйста, присоединяйтесьЧистка команды.

Категории