Java描述 LeetCode,516. Longest Palindromic Subsequence 最长回文子序列
大家好,我是河海哥,专注于后端,如果可以的话,想做一名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题,这里总的来说难度不是很大。继续加油!!河海哥,冲!至少做到,做过的以后能写出来。💪您的评论与赞是我的最大动力,如有错误还请不吝赐教,万分感谢。