回文アルゴリズムのまとめ

回文アルゴリズムのまとめ
最長回文子列

#
# @lc app=leetcode.cn id=5 lang=python3
#
# [5]       
#

# @lc code=start
class Solution:
    def longestPalindrome(self, s: str) -> str:
        size = len(s)
        if size < 2:
            return s
        
        #     1
        max_len = 1
        res = s[0]

        for i in range(size):
            palindrome_odd, odd_len = self.__center_spread(s, size, i, i)
            palindrome_even, even_len = self.__center_spread(s, size, i, i + 1)

            #            
            cur_max_sub = palindrome_odd if odd_len >= even_len else palindrome_even
            if len(cur_max_sub) > max_len:
                max_len = len(cur_max_sub)
                res = cur_max_sub

        return res

    def __center_spread(self, s, size, left, right):
        """
        left = right    ，           ，         
        right = left + 1    ，           ，         
        """
        i = left
        j = right

        while i >= 0 and j < size and s[i] == s[j]:
            i -= 1
            j += 1
        return s[i + 1:j], j - i - 1
        
# @lc code=end

エコーチェーン

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        slow,fast,prev = head,head,None
        #         
        while fast is not None:
            slow = slow.next
            fast = fast.next.next if fast.next is not None else fast.next
        #              
        while slow is not None:
            slow.next,slow,prev = prev,slow.next,slow
        #        
        while head and prev:
            if head.val != prev.val:
                return False
            head = head.next
            prev = prev.next
        return True

最長回文サブシーケンス

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        if not s:
            return 0
        #                base        。
        dp = [[0]*(n) for _ in range(n)]
        for i in range(n):
            dp[i][i] = 1
        for i in range(n-1,-1,-1):
            for j in range(i+1,n):
                if s[i] == s[j]:
                    dp[i][j] = dp[i+1][j-1]+2
                else:
                    dp[i][j] = max(dp[i+1][j],dp[i][j-1])
        return dp[0][-1]

最長回文サブシーケンス
回文であるため、2次元dp配列が必要であり、dp[i][j]はnums[i]からnums[j]までの最長回文シーケンス長を表す.したがってnums[i]=nums[j]であればdp[i][j]=dp[i+1][j-1]+2、そうでなければdp[i][j]=max(dp[i+1][j],dp[i][j-1])となり、小さなテクニックが必要になります.dpマトリクスを描いた後、dp[i][i]=1を発見したので、後順に遍歴したり、斜めに遍歴したりする必要があります.後順:for(int i=n-1;i>=0;i-)斜め:for(int l=2;l<=n;l+){{for(int j=i+1;jclass Solution: def longestPalindromeSubseq(self, s: str) -> int: n = len(s) if not s: return 0 # base 。 dp = [[0]*(n) for _ in range(n)] for i in range(n): dp[i][i] = 1 for i in range(n-1,-1,-1): for j in range(i+1,n): if s[i] == s[j]: dp[i][j] = dp[i+1][j-1]+2 else: dp[i][j] = max(dp[i+1][j],dp[i][j-1]) return dp[0][-1]