最长回文子序列
难度:
标签:
题目描述
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab" 输出：4 解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：
输入：s = "cbbd" 输出：2 解释：一个可能的最长回文子序列为 "bb" 。
提示：
1 <= s.length <= 1000s仅由小写英文字母组成
代码结果
运行时间: 1192 ms, 内存: 221.4 MB
/*
* 题目思路：
* 给定一个字符串s，找到最长的回文子序列的长度。
* 我们可以使用动态规划来解决这个问题，使用Java Stream优化部分操作。
* 与普通动态规划的解法类似，使用dp数组记录最长回文子序列的长度。
* 通过Stream流处理简化一些操作。
*/
import java.util.stream.IntStream;
public class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] dp = new int[n][n];
IntStream.range(0, n).forEach(i -> dp[i][i] = 1);
IntStream.range(1, n).forEach(len ->
IntStream.range(0, n - len).forEach(i -> {
int j = i + len;
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]);
}
})
);
return dp[0][n - 1];
}
}
解释
方法:
这个题解采用动态规划的思路来解决最长回文子序列问题。使用一个二维的备忘录memo来存储子问题的结果，避免重复计算。dp(i, j)表示字符串s在区间[i, j]内的最长回文子序列的长度。如果s[i]和s[j]相等，那么dp(i, j) = dp(i+1, j-1) + 2，否则dp(i, j) = max(dp(i+1, j), dp(i, j-1))。最终返回dp(0, len(s)-1)即为整个字符串s的最长回文子序列长度。
时间复杂度:
O(n^2)
空间复杂度:
O(n^2)
代码细节讲解
🦆
在动态规划中，为什么选择使用二维备忘录memo而不是简化为一维数组？
▷🦆
函数dp(i, j)在i > j时返回0的逻辑依据是什么？
▷🦆
在边界条件中，dp(i, i)返回1是基于什么考虑？
▷🦆
如何理解动态规划中的递推公式dp(i, j) = dp(i+1, j-1) + 2当s[i] == s[j]？
▷相关问题
最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：
输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd" 输出："bb"
提示：
1 <= s.length <= 1000s仅由数字和英文字母组成
回文子串
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：s = "abc" 输出：3 解释：三个回文子串: "a", "b", "c"
示例 2：
输入：s = "aaa" 输出：6 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示：
1 <= s.length <= 1000s由小写英文字母组成
统计不同回文子序列
给你一个字符串 s ，返回 s 中不同的非空回文子序列个数 。由于答案可能很大，请返回对 109 + 7 取余 的结果。
字符串的子序列可以经由字符串删除 0 个或多个字符获得。
如果一个序列与它反转后的序列一致，那么它是回文序列。
如果存在某个 i , 满足 ai != bi ，则两个序列 a1, a2, ... 和 b1, b2, ... 不同。
示例 1：
输入：s = 'bccb' 输出：6 解释：6 个不同的非空回文子字符序列分别为：'b', 'c', 'bb', 'cc', 'bcb', 'bccb'。 注意：'bcb' 虽然出现两次但仅计数一次。
示例 2：
输入：s = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba' 输出：104860361 解释：共有 3104860382 个不同的非空回文子序列，104860361 是对 109 + 7 取余后的值。
提示：
1 <= s.length <= 1000s[i]仅包含'a','b','c'或'd'