LeetCode-Longest Palindromic Subsequence

太过爱你忘了你带给我的痛 2022-03-20 04:46 116阅读 0赞

### 文章目录 ###

*  Longest Palindromic Subsequence
 *   *  题目描述
     *  思路分析
     *  C++实现
     *  Scala实现

版权声明：本文为博主原创文章，转载请注明原文出处！  
写作时间：2019-02-10 11:44:52

# Longest Palindromic Subsequence #

## 题目描述 ##

这是LeetCode的第516道题目：[516. Longest Palindromic Subsequence][]。

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:

One possible longest palindromic subsequence is “bbbb”.

**Example 2:**  
Input:

"cbbd"

Output:

One possible longest palindromic subsequence is “bb”.

题目要求我们计算出给定字符串中的最长回文序列（这里的序列不是一定要在给定字符串中连续排列的，就是挑出的单个字符按其在给定字符串中的顺序排列以后是回文即可）

## 思路分析 ##

其实，思路跟第647道题目[Palindromic Substrings][]是类似的，可以采用动态规划进行。但是因为回文序列不是给定字符串的连续子串，貌似不能使用中心扩散法求解。

使用动态规划，我们设`dp[i][j]`表示从第`i`个字符到到`j`个字符回文序列的长度，则有：

1.  当`s[i] == s[j]`时，`dp[i][j] = dp[i+1][j-1] + 2`
2.  当`s[i] != s[j]`时，`dp[i][j] = max(dp[i+1][j], dp[i][j-1])`

## C++实现 ##

class Solution {
    public:
        int longestPalindromeSubseq(string s) {
            const int length = s.length();
            vector<vector<int>> dp(length, vector<int>(length));
            for (auto i = length - 1; i >= 0; --i) {
                dp[i][i] = 1;
                for (auto j = i + 1; j < length; ++j) {
                    dp[i][j] = s[i] == s[j] ?
                            dp[i + 1][j - 1] + 2 :
                            max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
            return dp[0][length - 1];
        }
    };

## Scala实现 ##

Scala版本是对C++版本的翻译

object Solution {
      def longestPalindromeSubseq(s: String): Int = {
        val length = s.length
        val dp = Array.ofDim[Int](length, length)
        for (i <- length - 1 to 0 by -1) {
          dp(i)(i) = 1
          for (j <- i + 1 until length) {
            dp(i)(j) = if (s(i) == s(j)) dp(i + 1)(j - 1) + 2
            else math.max(dp(i + 1)(j), dp(i)(j - 1))
          }
        }
        return dp(0)(length - 1)
      }
    }

[516. Longest Palindromic Subsequence]: https://leetcode.com/problems/longest-palindromic-subsequence/
[Palindromic Substrings]: https://leetcode.com/problems/palindromic-substrings/