[Перфокарта ежедневного алгоритма] Самая длинная палиндромная подстрока

искусственный интеллект алгоритм
[Перфокарта ежедневного алгоритма] Самая длинная палиндромная подстрока

«Это третий день моего участия в ноябрьском испытании обновлений. Подробную информацию об этом событии см.:Вызов последнего обновления 2021 г.".

【Ежедневные пробные серии】LeetCode200 простых вопросов

Описание темы

дает вам строкуs,оказаться sСамая длинная подстрока палиндрома в .

Пример 1:

Ввод: s = "бабад"
Вывод: "баб"
Пояснение: «аба» — это тоже ответ, соответствующий смыслу вопроса.

Пример 2:

Ввод: s = "cbbd"
Выход: "бб"

Пример 3:

Вход: с = "а"
Выход: "а"

Пример 4:

Вход: с = "ас"
Выход: "а"

намекать

  • 1 <= s.length <= 1000
  • sСостоит только из цифр и английских букв (верхнего и/или нижнего регистра)

Идеи решения проблем

1. Законы о насилии
Метод грубой силы всегда является самым простым решением, но скорость его неудовлетворительна. два этажаforПереберите все случаи, чтобы найти наибольшую подстроку палиндрома. Показать время ожидания при отправке кода. Это так расстраивает!

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        length = len(s)
        # 将首字符作为max_str的初始值
        max_str = s[0]
        for i in range(length - 1):
            for j in range(i + 1, length):
            	# 如果s[i: j + 1]是回文子串并且长度大于len(max_str),就将其替换
                if s[i: j + 1] == s[i: j + 1][::-1] and j - i + 1 > len(max_str):
                    max_str = s[i: j + 1]
        return max_str

Временная сложность: O(n³)
Космическая сложность: O(1)

2. Метод центральной диффузии
В соответствии с симметрией палиндрома мы можем указать его центр для цикла и судить, равны ли левый и правый символы каждый раз.

class Solution(object):
    def expandAroundCenter(self, s, left, right):
        max_len = 0
        # 退出条件:越界
        while left >= 0 and right < len(s):
            if s[left] == s[right]:
                left -= 1
                right += 1
            else:
                break
        return right - left - 1


    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        rst = s[0]
        # 遍历中心点
        for i in range(len(s) - 1):
        	# 通过expandAroundCenter方法获取最大回文串长度
        	# 奇数时,left = right = i
            odd_len = self.expandAroundCenter(s, i, i)
            # 偶数时,left = i,right = i + 1
            even_len = self.expandAroundCenter(s, i, i + 1)
            #获取最大len
            max_len = max(odd_len, even_len)
            if max_len > len(rst):
            	# 获取回文串起始下标
                begin = i - (max_len - 1) // 2
                rst = s[begin: begin + max_len]
        return rst

Временная сложность: O(n²)
Космическая сложность: O(1)

Сегодняшняя регистрация завершена, текущий прогресс — 8/200.