一、题目描述

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

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

示例 1:

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

示例 2:

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

提示:

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

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 最长回文子序列( LeetCode 516 ):https://leetcode-cn.com/problems/longest-palindromic-subsequence
class Solution {
    public int longestPalindromeSubseq(String s) {

        // 获取字符串 s 的长度
        int length = s.length();

        // 设置数组 dp,用来存储字符串 s 的最长的回文子序列的长度
        // dp[0][0] 表示字符串 s 第 0 个字符和字符串 s 第 0 个字符之间的最长的回文子序列的长度
        // dp[2][3] 表示字符串 s 第 2 个字符和字符串 s 第 3 个字符之间的最长的回文子序列的长度
        // dp[i][j] 表示字符串 s 第 i 个字符和字符串 s 第 j 个字符之间的最长的回文子序列的长度
        // i 最大值为 length - 1
        int[][] dp = new int[length][ length];

        // dp[0][0] 表示字符串 s 第 0 个字符和字符串 s 第 0 个字符之间的最长的回文子序列的长度
        // dp[3][3] 表示字符串 s 第 3 个字符和字符串 s 第 3 个字符之间的最长的回文子序列的长度
        // dp[i][i] 表示字符串 s 第 i 个字符和字符串 s 第 i 个字符之间的最长的回文子序列的长度
        // 此时,这个区间的字符只有一个,最长的回文子序列的长度为 1
        for (int i = 0; i < length; i++) {
            dp[i][i] = 1;
        }

        // i 从字符串 s 的【尾部】开始向前遍历,j 从 i + 1 开始向后遍历
        // 不断的逼近二维数组最右上角的位置,即求 dp[0][length - 1]
        for (int i = length - 1; i >= 0; i--) {

           for( int j = i + 1 ; j < length ; j++ ){

               // 如果发现 s.charAt(i) == s.charAt(j)
               if (s.charAt(i) == s.charAt(j)) {

                   // dp[i][j] 表示字符串 s 第 i 个字符和字符串 s 第 j 个字符之间的最长的回文子序列的长度
                   // dp[i][j] 表示字符串 s 第 i + 1 个字符和字符串 s 第 j - 1 个字符之间的最长的回文子序列的长度
                   // 由于扩充的两个字符相等,意味着最长的回文子序列的长度加 2
                   dp[i][j] = dp[ i + 1 ][ j - 1 ] + 2;

               }else{

                   // 字符区间 s[i..j] 里最长回文子序列的长度
                   // 1、去掉头以后的区间的最长的回文子序列的长度,即 dp[i + 1][j]
                   // 2、去掉尾以后的区间的最长的回文子序列的长度,即  dp[i][j - 1]
                   // 二者取最大值
                   dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
               }
           }

        }

        // 最右上角的值就是结果
        return dp[0][length - 1];

    }
}

2、C++ 代码

3、Python 代码

四、动画理解(没有声音)

发表评论

邮箱地址不会被公开。 必填项已用*标注