Java描述 LeetCode,516. Longest Palindromic Subsequence 最长回文子序列

wuchangjian2021-11-15 09:45:55编程学习

大家好,我是河海哥,专注于后端,如果可以的话,想做一名code designer而不是普通的coder,一起见证河海哥的成长,您的评论与赞是我的最大动力,如有错误还请不吝赐教,万分感谢。

1-1:题目

Given a string s, find the longest palindromic subsequence’s length in s.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".

Example 2:

Input: s = "cbbd"
Output: 2
Explanation: One possible longest palindromic subsequence is "bb".

Constraints:

1 <= s.length <= 1000
s consists only of lowercase English letters.

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-palindromic-subsequence

1-2:idea

这道题主要和Java描述 LeetCode,647. Palindromic Substrings 回文子串,这道题形成鲜明的对比,解题思路是差不多的,唯一的区别就是647题是回文子串,就是说必须是连续的,这里的516题是子序列,可以不连续的。有了上一题的经验,我们很容易想到dp状态。

  • dp状态:dp[i][j]:s[i:j](左包含右包含)的最长回文子序列的长度是dp[i][j]。
  • 状态转移方程:
    • s[i] == s[j],往里缩,dp[i][j] = dp[i+1][j-1] + 2;+2是因为s[i],s[j]两个相等的字符要算上的,这样得到新的最优解。
    • s[i] != s[j],两种手段,i往里面缩或者j往里面缩,取最大值, dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]),为什么647题不相等就不用继续考虑呢?因为647题要求是连续的回文子串,不相等了i,j再往里面考虑没有意义了,但这边不一样,这里是可以不连续的,可以继续往里面考虑。这边不理解可以先看看上面的647题,两道题对比起来做,会很好。
  • 遍历顺序:从下往上,从左到右。和647一样。
  • 初始化:这里根据状态转移方程,可以对i == j的部分初始化,也就是打表时候的斜对角。

1-3:代码

public static int longestPalindromeSubseq(String s) {
   int n = s.length();

   int[][] dp = new int[n][n]; // 0~n-1

   // initialization
   for (int i = 0; i < n; i++) {
       dp[i][i] = 1;
   }

   for (int i = n - 2; i >= 0; i--) {
       for (int j = i + 1; j < n; j++) {
           if (s.charAt(i) == s.charAt(j)) {
               dp[i][j] = dp[i + 1][j - 1] + 2;
           } else {
               dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
           }
       }
   }
   System.out.println(Arrays.deepToString(dp));
   return dp[0][n - 1];
}

同样要注意,i<=j 这个是整个代码中必须要注意到的,斜对角的左下方是不用考虑的。(这里和647题是一样的)

1-4:代码小优化

上面的代码其实不够完美,我们可以把初始化放进外侧循环,一边遍历一遍初始化。还有一个优化点,就是s.charAt(i),其实可以放到外侧循环,提前保存好,这样就不用每次内循环去做s.charAt(i)这个操作了,这个也是一个小优化点。
在这里插入图片描述
优化代码如下:

public static int longestPalindromeSubseq2(String s) {
    int n = s.length();

    int[][] dp = new int[n][n]; // 0~n-1

    for (int i = n - 1; i >= 0; i--) {
        dp[i][i] = 1;
        char sc = s.charAt(i);
        for (int j = i + 1; j < n; j++) {
            if (sc == s.charAt(j)) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    
    return dp[0][n - 1];
}

打表:
String s = "bbbab";

\ j 0  1  2  3  4
i \ b  b  b  a  b
0 b[1, 2, 3, 3, 4]
1 b[0, 1, 2, 2, 3]
2 b[0, 0, 1, 1, 3]
3 a[0, 0, 0, 1, 1]
4 b[0, 0, 0, 0, 1]

1-5:总结

这道题主要和647对比起来,属于差不多的题,只是一个是子序列(不连续),一个是子串(连续),如果你做了647题,这里总的来说难度不是很大。继续加油!!河海哥,冲!至少做到,做过的以后能写出来。💪您的评论与赞是我的最大动力,如有错误还请不吝赐教,万分感谢。

相关文章

Python 户外俱乐部·登顶纪念证书生成器

Python 户外俱乐部·登顶纪念证书生成器

每个周末,我喜欢和户外俱乐部的小伙伴们一起到野外登山徒步,一...

Scala

...

零基础学python保姆级教程——if语句

上一篇我们讲到了倒叙,接下来我们讲元组,有关于列表ÿ...

MySQL 性能优化一

优化方向   硬件和OS调优 、MySql调优 、架构优化。对架构的优化对mysql的...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。