Leetcode 516 Longest Palindromic Subsequence

发表于 |

给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。

示例 1:
输入:
“bbbab”
输出:
4
一个可能的最长回文子序列为 “bbbb”。

示例 2:
输入:
“cbbd”
输出:
2
一个可能的最长回文子序列为 “bb”。

分析：

  1. 这道题如果能想到定义dp[i][j]表示s[i:j+1]的最长回文子序列长度的话就很简单了，所以在这里的话，我更想去说一下我是怎么想到要用dp以及这样来定义dp的，我认为这才是有帮助的
  2. 看到示例1的时候，’bbbab’，我想首先依次遍历，然后看此时遍历的字符有没有在之前出现过，如果出现过，以这个两个相同字符为边界，看是否能找到一个回文串，那么中间的字符是什么状态呢？是本身就是回文串呢或者说其子串包含回文串呢，想到这一步我突然意识到，这不就是问题的解依赖于其子问题的解吗，于是想到用dp来解决
  3. 那么怎么定义dp呢，因为按照我的思路是固定住两边观察中间，所以我定义一个二维dp，那么上面说的那种情况就可以写成dp[i][j] = dp[i+1][j-1] + 2，到这里豁然开朗，我知道自己没想错……

思路：

  1. if s[i] == s[j]: dp[i][j] = dp[i+1][j-1] + 2
  2. else: dp[i][j] = max(dp[i+1][j], dp[i][j-1])
  3. 我是用斜向遍历的，对于示例1：
    1. (0,1)->(1,2)->(2,3)->(3,4)
    2. (0,2)->(1,3)->(2,4)
    3. (0,3)->(2,4)
    4. (0,4) # 最后结果
  4. 实际上你可以用从最后一层向上遍历，那样的代码应该是最优美的！
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    class Solution(object):
        def longestPalindromeSubseq(self, s):
            """
            :type s: str
            :rtype: int
            """
            # dp[i][j] reps from i to j,the length of LPS
            if s == s[::-1]: return len(s) # this code helps my runtime decrease from 1500ms to 500ms,beats 99%
            n = len(s)
            dp = [[1]*n for _ in range(n)]
            # 处理斜向遍历时i,j的间隔
            gap = 1
            for index in range(n-1):
                i,j = 0,gap	
                while j < n:
                    if gap == 1:
                        dp[i][j] += s[i] == s[j]
                    elif 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])
                    i += 1
                    j += 1
                gap += 1
            return dp[0][n-1]# 返回dp中最大的数，实际也就是这个