提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

Leetcode学习计划之动态规划入门day17(5,516)

LeetCode规划学习入门 动态 计划
2023-09-14 09:01:30 时间

目录

5. 最长回文子串

问题描述

思路与算法1: 动态规划

思路解法2：中心扩展算法

516. 最长回文子序列

问题描述

思路与算法

5. 最长回文子串

问题描述

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

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

示例 2：

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

提示：

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成

思路与算法1: 动态规划

        这道题目之前做过（Leetcode0005. 最长回文子串(medium, 枚举遍历，动态规划)），不过当时的动态规划解法很悲惨地超时了。这里来考虑一下如何改进。考虑以下两个小的改进：

  • 直接用二维数组存储，而不是用dict，dict查询不可能比数组索引查询更快
  • 每次更新最大值时，只记录下对应左右边界，而不是直接更新结果字符串。字符串的赋值应该比两个整数的赋值的开销要更大吧

class Solution:
    def longestPalindrome(self, s: str) -> str:
        N = len(s)
        p = [[False]*N for _ in range(N)]

        # 长度为1的字串都是回文串
        for i in range(N):
            p[i][i] = True
        
        maxlen = 1
        l0,r0  = 0,0
        # 对子串长度从小(>=2)到大进行扫描
        # 由于先扫描了较短的子串，扫描到较长子串判断时所需要的信息就全部具备了
        for L in range(2,N+1):
            #对左边界进行扫描
            for l in range(0,N-L+1):
                r = l + L - 1 # l:left, r: right
                if s[r] == s[l]:
                    if L==2:
                        p[l][r] = True
                    else:
                        p[l][r] = p[l+1][r-1]
                if p[l][r]:
                    if r-l+1 > maxlen:
                        maxlen = r-l+1
                        l0,r0  = l,r
        #print(maxlen)
        return s[l0:r0+1]

        

        执行用时：5948 ms, 在所有 Python3 提交中击败了41.25%的用户

        内存消耗：23 MB, 在所有 Python3 提交中击败了15.37%的用户

        比上一次的有所改进。

思路解法2：中心扩展算法

        我们仔细观察一下方法一中的状态转移方程：

        

        找出其中的状态转移链：

                P(i,j)\leftarrow P(i+1,j-1)\leftarrow P(i+2,j-2)\leftarrow \cdots \leftarrow某一边界情况 

        可以发现，所有的状态在转移的时候的可能性都是唯一的，这是由回文串的对称性所要求的。也就是说，我们可以从每一种边界情况开始「扩展」，也可以得出所有的状态对应的答案。 

        比如说，可以从长度为1的边界情况s[k]开始从中心向两侧对称生长得到所有以索引k为中心的子串的回文判断结果。也可以从长度为2的边界情况s[k:k+2]开始从中心向两侧对称生长得到所有长度为偶数的包含s[k:k+2]为中心的字串的回文判断情况。

        而且，在向两侧对称生长的过程中，碰到一个False的判断就可以提前退出了。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        N = len(s)
        p = [[False]*N for _ in range(N)]

        maxlen = 1
        l0,r0  = 0,0
        # 长度为1的字串都是回文串
        for i in range(N):
            p[i][i] = True
            #以i为中心向两侧对称扩展
            for k in range(1,N):
                if i-k < 0 or i+k > N-1:
                    break
                if s[i+k] == s[i-k]:
                    p[i-k][i+k] = True
                    if 2*k+1 > maxlen:
                        maxlen = 2*k+1
                        l0,r0  = i-k,i+k                    
                else:
                    break

        # 长度为2的字串
        for i in range(N-1):
            #以(i,i+1)为中心向两侧对称扩展
            for k in range(0,N):
                if i-k < 0 or i+k+1 > N-1:
                    break
                if s[i+k+1] == s[i-k]:
                    p[i-k][i+k+1] = True
                    if 2*k+2 > maxlen:
                        maxlen = 2*k+2
                        l0,r0  = i-k,i+k+1   
                else:
                    break
        return s[l0:r0+1]

        执行用时：1812 ms, 在所有 Python3 提交中击败了55.05%的用户

        内存消耗：22.9 MB, 在所有 Python3 提交中击败了21.51%的用户

        比上一种方法有进一步的改进，但是仍然不够理想。

516. 最长回文子序列

问题描述

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

示例 2：

输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

提示：

  • 1 <= s.length <= 1000
  • s 仅由小写英文字母组成

思路与算法

        与上一题的区别在于，子串是要求连续的，子序列不要求连续。

        考虑f(i,j)表示子字符串从索引i到索引j（包含）之间的子字符串（s[i:j+1]）中包含的最长回文子序列的长度，首先根据s[i]与s[j]是否相等可以分为以下两种情况：

  • case1: s[i]==s[j]。很显然，最长回文子序列一定包含s[i]和s[j]，因此有f(i,j) = f(i+1,j-1) + 2
  • case2: s[i]!=s[j]。进一步可以分解为以下三种子情况，结果为三种子情况中的最大者
    • case2-1: 最长回文子序列包含s[i]但是不包含s[j]
    • case2-2: 最长回文子序列包含s[j]但是不包含s[i]
    • case2-3: 既不包含s[i]也不包含s[j]

        在case2-1中，既然包含s[i]，满足该条件的最长回文子序列的最右端也必然是等于s[i]的字符，因此可以从右向左搜索与s[i]相等的第一个字符，这样它就变成了case1那种情况了。

        case2-2同理，只不过是从左向右搜索寻找第一个与s[j]相同的字符

        case2-3最简单，直接就变成了f(i+1,j-1)

        baseline case: 很显然长度为1的字串所包含的最长回文字串长度为1，很显然长度为0的字串所包含的最长回文字串长度为0.

from typing import List
class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        
        memo= dict()
        def dp(i,j):
            # print('dp: i = {0}, j={1}'.format(i,j))
            if (i,j) in memo:
                return memo[i,j]
            if i==j:
                return 1
            if i>j:
                return 0
            
            if s[i]==s[j]:
                memo[(i,j)] = dp(i+1,j-1) + 2
                return memo[(i,j)]
            else:
                # case2-1
                k = j-1
                tmp1 = 1
                while k > i:
                    if s[k] == s[i]:
                        tmp1 = dp(i+1,k-1) + 2
                        break
                    else:
                        k = k - 1
                # case2-2
                k = i+1
                tmp2 = 1
                while k < j:
                    if s[k] == s[j]:
                        tmp2 = dp(k+1,j-1) + 2
                        break
                    else:
                        k = k + 1
                # case2-3
                tmp3 = dp(i+1,j-1)
                memo[(i,j)] = max(tmp1,tmp2,tmp3)
                return memo[(i,j)]
            
        return dp(0,len(s)-1)
                
if __name__ == "__main__":
    
    sln = Solution()    

    s = "bb"
    print(sln.longestPalindromeSubseq(s))
    
    s = "bbbab"
    print(sln.longestPalindromeSubseq(s))
    
    s = "cbbd"
    print(sln.longestPalindromeSubseq(s))
    
    s= "abcdef"
    print(sln.longestPalindromeSubseq(s))

        执行用时：1992 ms, 在所有 Python3 提交中击败了15.85%的用户

        内存消耗：117.3 MB, 在所有 Python3 提交中击败了5.05%的用户

        性能惨点儿，但是好歹是亲生原创^-^

        官解如下（确实更加简洁优美，关键是状态转移定义得合理）：

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        dp = [[0] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            dp[i][i] = 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][n - 1]

        执行用时：1132 ms, 在所有 Python3 提交中击败了84.69%的用户

        内存消耗：31.4 MB, 在所有 Python3 提交中击败了36.88%的用户

        回到总目录：笨牛慢耕的Leetcode每日一题总目录(动态更新。。。)

        

相关文章