专栏首页给永远比拿愉快LeetCode-Longest Palindromic Subsequence
原创

LeetCode-Longest Palindromic Subsequence

版权声明:本文为博主原创文章,转载请注明原文出处!

写作时间: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:

4

One possible longest palindromic subsequence is "bbbb".

Example 2:

Input:

"cbbd"

Output:

2

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)
  }
}

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Minimum Falling Path Sum

    Given a square array of integers A, we want the minimum sum of a falling paththr...

    卡尔曼和玻尔兹曼谁曼
  • LeetCode-Palindromic Substrings

    Given a string, your task is to count how many palindromic substrings in this st...

    卡尔曼和玻尔兹曼谁曼
  • Minimum Cost For Tickets

    In a country popular for train travel, you have planned some train travelling on...

    卡尔曼和玻尔兹曼谁曼
  • 详解 leetcode 221 题:最大正方形

    在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。

    帅地
  • Leetcode 516. 最长回文子序列

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

    zhipingChen
  • 漫画:BAT必考题目 (如何压缩状态完成不同路径题目)

    不同路径:一个机器人位于一个 m x n 网格的左上角,起始点在下图中标记为“Start”。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角,在下...

    程序员小浩
  • LeetCode 343. 整数拆分(DP)

    给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

    Michael阿明
  • LeetCode 123. 买卖股票的最佳时机 III(动态规划)

    Michael阿明
  • Leetcode 32 Longest Valid Parentheses DP好题

    Given a string containing just the characters '(' and ')', find the length of ...

    triplebee
  • LeetCode 123. Best Time to Buy and Sell Stock III

    https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/description/

    ShenduCC

扫码关注云+社区

领取腾讯云代金券