Skip to content

Latest commit

 

History

History
250 lines (177 loc) · 5.22 KB

0516._Longest_Palindromic_Subsequence.md

File metadata and controls

250 lines (177 loc) · 5.22 KB

516. Longest Palindromic Subsequence

难度: Medium

刷题内容

原题连接

内容描述

Given a string s, find the longest palindromic subsequence's length in s. You may assume that the maximum length of s is 1000.

Example 1:
Input:

"bbbab"
Output:
4
One possible longest palindromic subsequence is "bbbb".
Example 2:
Input:

"cbbd"
Output:
2
One possible longest palindromic subsequence is "bb".

解题方案

思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(N^2)******

其实就是求s和s[::-1]的最长公共子序列

beats 49.81%

class Solution:
    def longestPalindromeSubseq(self, s):
        """
        :type s: str
        :rtype: int
        """
        if s == s[::-1]:
            return len(s)
        return self.longestCommonSubsequence(s, s[::-1])

        
    def longestCommonSubsequence(self, s1, s2):  # O(mn)
        m, n = len(s1), len(s2)
        dp = [[0] * (n + 1) for i in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s1[i - 1] == s2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[-1][-1]

思路 2 - 时间复杂度: O(N^2)- 空间复杂度: O(N^2)******

记忆化搜索，Top down，beats 5.99%，有的时候又会超时过不了，奇怪

python2死都AC不了，python3偶尔能AC

class Solution(object):
    def longestPalindromeSubseq(self, s):
        """
        :type s: str
        :rtype: int
        """
        cache = {}
        def helper(s, i, j):
            if (i, j) in cache:
                return cache[(i,j)]
            if i > j:
                return 0
            elif i == j:
                return 1
            else:
                if s[i] == s[j]:
                    cache[(i,j)] = helper(s, i+1, j-1) + 2
                else:
                    cache[(i,j)] = max(helper(s, i, j-1), helper(s, i+1, j))
            return cache[(i,j)]
        
        return helper(s, 0, len(s)-1)

思路 3 - 时间复杂度: O(N^2)- 空间复杂度: O(N^2)******

改进版记忆化搜索，beats 94.01%

class Solution:
    def longestPalindromeSubseq(self, s):
        """
        :type s: str
        :rtype: int
        """
        if s == s[::-1]:
            return len(s)
        cache = {}
        def helper(s):
            if s not in cache:
                max_len = 0    
                for c in set(s):
                    i, j = s.find(c), s.rfind(c)
                    max_len = max(max_len, 1 if i == j else 2 + helper(s[i+1:j]))
                cache[s] = max_len
            return cache[s]
        return helper(s)

思路 4 - 时间复杂度: O(N^2)- 空间复杂度: O(N^2)******

Bottom up

DP, beats 92.51%

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

思路 5 - 时间复杂度: O(N^2)- 空间复杂度: O(N)******

dp[i] : longest palindrom subsequence start from i

这里的空间优化我确实没怎么看懂，希望有看懂的可以给我留言

beats 94.01%

class Solution:
    def longestPalindromeSubseq(self, s):
        """
        :type s: str
        :rtype: int
        """
        if s == s[::-1]:
            return len(s)
        dp = [1] * len(s)
        for i in range(1, len(s)):
            length = 0
            for j in range(i-1, -1, -1):
                tmp = dp[j]
                if s[j] == s[i]:
                    dp[j] = length + 2
                length = max(length, tmp)
        return max(dp)

思路 6 - 时间复杂度: O(N^2)- 空间复杂度: O(N^2)******

参考A typical way to solve palindrome problems

beats 88.76%

class Solution:
    def longestPalindromeSubseq(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s or len(s) == 0:
            return 0
        if s == s[::-1]:
            return len(s)
        dp = [[0] * len(s) for i in range(len(s))]
        for i in range(len(s)):
            dp[i][i] = 1
        for i in range(len(s)-1):
            if s[i] == s[i+1]:
                dp[i][i+1] = 2
            else:
                dp[i][i+1] = 1

        for gap in range(2, len(s)):
            for i in range(len(s)-gap):
                j = i + gap
                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]