求最长回文子序列长度问题
求最长回文子序列长度问题
作者:Grey
原文地址:
题目描述
给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。题目链接见:LeetCode 516. Longest Palindromic Subsequence
暴力解
定义递归函数
int process(int i, int j, char[] str)
递归含义是:str 这个字符串从 i 到 j,最长回文子序列长度是多少。
主函数只需要调用
return process(0, str.length - 1, str);
即为要求的答案。
接下来看递归函数的实现
首先是 base case,显然有如下两个结论:
结论1:当i == j
的时候,说明只有一个字符,最长回文子序列长度就是 1;
结论2:当i == j - 1
的时候,如果str[i] == str[j]
,则最长回文子序列的长度就是 2, 否则就是 1;
接下来就是普遍情况:
要求i……j
之间的最长回文子序列的长度,有如下三种情况
情况1,不考虑 i 位置的字符,则i……j
之间的最长回文子序列的长度就是i+1……j
之间的最长回文子序列长度。
情况2,不考虑 j 位置的字符,则i……j
之间的最长回文子序列的长度就是i……j-1
之间的最长回文子序列的长度。
情况3,当str[i] == str[j]
的时候,i……j
之间的最长回文子序列的长度就是i+1……j-1
之间的最长回文子序列的长度加 2。
以上三种情况求最大值,就是i……j
之间的最长回文子序列的长度。
暴力解法的完整代码如下
class Solution {
public static int longestPalindromeSubseq(String s) {
if (s == null || s.length() < 1) {
return 0;
}
char[] str = s.toCharArray();
return process(0, str.length - 1, str);
}
// i...j的最长回文子序列是多少
public static int process(int i, int j, char[] str) {
if (i == j) {
return 1;
}
if (i == j - 1) {
return str[i] == str[j] ? 2 : 1;
}
int p1 = process(i + 1, j, str);
int p2 = process(i, j - 1, str);
int p3 = (str[i] == str[j] ? 2 : 0) + process(i + 1, j - 1, str);
return Math.max(p1, Math.max(p2, p3));
}
}
LeetCode 上这个解法会直接超时
动态规划
通过暴力递归方法
public static int process(int i, int j, char[] str) {
...
int p1 = process(i + 1, j, str);
int p2 = process(i, j - 1, str);
... process(i + 1, j - 1, str);
....
}
我们可以得到一个结论,原问题是一个二维数组规模的问题,使用一个二维数组就可以把整个递归中的解保存下来,二维数组定义如下
int[][] dp = new int[s.length()][s.length()];
dp[i][j]
就是递归函数process(i,j,str)
的含义,即:str 这个字符串从 i 到 j,最长回文子序列长度是多少。
且任何一个(i,j)
位置依赖三个位置的值,即:(i,j-1)
,(i+1,j)
,(i+1,j-1)
二维数组的对角线位置的值都是 1,因为对角线i == j
,只有一个字符,最大回文子序列就是 1,
接下来按照递归含义依次填好每个二维数组格子的值,说明见注释
for (int i = 0; i < s.length(); i++) {
// 对角线都是1
dp[i][i] = 1;
if (i != s.length() - 1) {
// 对角线上一条线 不是 1 就是 2
dp[i][i + 1] = str[i] == str[i + 1] ? 2 : 1;
}
}
// 普遍位置
for (int index = 2; index < s.length(); index++) {
int i = 0;
int j = index;
while (j < s.length()) {
int p1 = dp[i + 1][j];
int p2 = dp[i][j - 1];
int p3 = (str[i] == str[j] ? 2 : 0) + dp[i + 1][j - 1];
dp[i][j] = Math.max(p1, Math.max(p2, p3));
i++;
j++;
}
}
// 返回dp[0][s.length() - 1]: 即 整个字符串的最长回文子序列的长度
return dp[0][s.length() - 1];
完整代码如下
class Solution {
public static int longestPalindromeSubseq(String s) {
if (s == null || s.length() < 1) {
return 0;
}
char[] str = s.toCharArray();
int[][] dp = new int[s.length()][s.length()];
for (int i = 0; i < s.length(); i++) {
dp[i][i] = 1;
if (i != s.length() - 1) {
dp[i][i + 1] = str[i] == str[i + 1] ? 2 : 1;
}
}
for (int index = 2; index < s.length(); index++) {
int i = 0;
int j = index;
while (j < s.length()) {
int p1 = dp[i + 1][j];
int p2 = dp[i][j - 1];
int p3 = (str[i] == str[j] ? 2 : 0) + dp[i + 1][j - 1];
dp[i][j] = Math.max(p1, Math.max(p2, p3));
i++;
j++;
}
}
return dp[0][s.length() - 1];
}
}
使用最大公共子序列来解
还有更多的思路可以解这个题目,比如:一个字符串和它的逆序串的最大公共子序列就是这个串的最长回文子序列,不赘述,直接看代码
class Solution {
public int longestPalindromeSubseq(String s) {
char[] str1 = s.toCharArray();
int n = str1.length;
char[] str2 = new char[n];
for (char str : str1) {
str2[--n] = str;
}
return longestCommonSubsequence2(str1, str2);
}
// 最长公共子序列
public int longestCommonSubsequence2(char[] str1, char[] str2) {
if ((null == str1 || str1.length == 0) || str2 == null || str2.length == 0) {
return 0;
}
int m = str1.length;
int n = str2.length;
int[][] dp = new int[m][n];
dp[0][0] = str1[0] == str2[0] ? 1 : 0;
for (int i = 1; i < n; i++) {
dp[0][i] = str1[0] == str2[i] ? 1 : dp[0][i - 1];
}
for (int i = 1; i < m; i++) {
dp[i][0] = str1[i] == str2[0] ? 1 : dp[i - 1][0];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
if (str1[i] == str2[j]) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
} else {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1]);
}
}
}
return dp[m - 1][n - 1];
}
}
其中int longestCommonSubsequence2(char[] str1, char[] str2)
方法就是求两个字符串的最长公共子序列的动态规划解法。
更多
相关文章
- 二面蚂蚁金服(交叉面),已拿offer,Java岗定级阿里P6
- Wolfram Mathematica 13 for Mac(科学计算软件)
- 根据访问请求客户端类型自动跳转到对应的页面地址,自动跳转到手机页面
- iframe页面嵌套提示X-Frame-Options问题
- 关于vue项目多页面的配置
- Frameset框架,在同一个浏览器窗口中显示不止一个页面
- 关于数据存储引擎结构,没有比这篇更详细的
- 如何让知识图谱告诉你“故障根因”
- SpringBoot写后端接口,看这一篇就够了!
- 我敢说,这个版本的斗地主你肯定没玩过?
- 云图说 | 华为云GPU共享型AI容器,让你用得起,用得好,用的放心
- 案例解析丨 Spark Hive 自定义函数应用
- 实践案例丨基于 Raft 协议的分布式数据库系统应用
- js面向对象
- 5 分钟带你掌握 Makefile 分析
- 云小课 |选定合适的证书,做“有证”的合规域名
- LiteOS间歇计算技术:IOT终端真正感受“电量自由”
- 超酷! Atlas给黑白视频“上色”
- GaussDB(DWS)应用实战:对被视图引用的表进行DDL操作
- 干货:不同场景容器内获取客户端源IP的方法