5. Longest Palindromic Substring

Leetcode 问题: 5. Longest Palindromic Substring
Categories:
Tags:

题目

Given a string s, return the longest palindromic substring in s.

回传最长的对称字串

example 1

Input: s = “babad” Output: “bab” Note: “aba” is also a valid answer.

example 2

Input: s = “cbbd” Output: “bb”

演算法原理

Longest palindromic substring | Dynamic programming

LeetCode 5. Longest Palindromic Substring (Algorithm Explained)

答案

Python

class Solution:
    def longestPalindrome(self, check_text: str) -> str:
        # 字串长度
        check_text_length = len(check_text)
        # 文字不重複字串
        check_text_set = set(check_text)

        if check_text_length <= 1 or len(check_text_set) == 1:
            # 若字串长度小于 1，或者字串为重複字串，直接将字串回传
            return check_text

        # manacher 检查字串，将字串加入 # 符号，强制将字串变为奇数长度字串
        # baba  => b#a#b#a
        # babad => b#a#b#a#d
        manacher_check_text = '#'.join(check_text)
        # manacher 检查字串长度
        manacher_check_text_length = len(manacher_check_text)
        manacher_check_text_range = range(1, manacher_check_text_length)
        # 对称字串长度对应表
        palindrome_length_mapping_table = [0] * manacher_check_text_length

        # 最长对称文字检查长度
        max_check_text_length: int = int(manacher_check_text_length / 2) + 1
        for check_text_length in range(1, max_check_text_length):
            # 设定下一个检查的文字范围
            manacher_next_check_text_range = []
            for check_text_position in manacher_check_text_range:
                # 检查文字位置
                # 检查文字位置，前一个检查文字长度位置
                check_text_previous_text_position = check_text_position - check_text_length
                # 检查文字位置，后一个检查文字长度位置
                check_text_next_text_position = check_text_position + check_text_length

                if check_text_previous_text_position < 0 or check_text_next_text_position >= manacher_check_text_length:
                    # 若字串索引超过字串长度，不检查
                    continue

                if manacher_check_text[check_text_previous_text_position] != manacher_check_text[
                    check_text_next_text_position]:
                    # 若字串前后不相等，继续检查下一个
                    continue

                # 字串相等，将此位置纪录，下个回合继续做检查
                manacher_next_check_text_range.append(check_text_position)

                if manacher_check_text[check_text_previous_text_position] == '#':
                    # 若为 manacher 字串符号，跳过不纪录
                    continue

                # 纪录非 # 字串，文字重複字串位置的长度
                palindrome_length_mapping_table[check_text_position] = check_text_length

            # 设定下一个字串检查范围，仅需检查目前有重複出现字串位置即可
            manacher_check_text_range = manacher_next_check_text_range

        # 最长文字长度出现位置
        max_text_length_position = 0
        # 最长文字长度
        max_text_length = 0
        for text_position, text_length in enumerate(palindrome_length_mapping_table):
            if text_length > max_text_length:
                # 若文字长度大于最大文字长度，设定此位置及长度为最长长度
                max_text_length = text_length
                max_text_length_position = text_position

        # 取出最长对称字串，并去除特殊标记「#」
        longest_palindrome_check_text = manacher_check_text[
                                        max_text_length_position - max_text_length:max_text_length_position + max_text_length + 1].replace(
            '#', '')

        return longest_palindrome_check_text


if __name__ == '__main__':
    # begin
    s = Solution()
    print(s.longestPalindrome('babad'))

参考资料