【算法】【递归与动态规划模块】两个字符串的最长公共子数组
前言
当前所有算法都使用测试用例运行过,但是不保证100%的测试用例,如果存在问题务必联系批评指正~
在此感谢左大神让我对算法有了新的感悟认识!
问题介绍
原问题
给定str1和str2两个字符串,求两个字符串的最长公共子数组,不是最长公共序列。
如:
str1:1AB2345CD str2:12345EF
结果:2345
解决方案
参考:https://swzhao.blog.csdn.net/article/details/127585231
原问题:
1、设计dp[i][j] 代表 最长子数组以str1[i]和str2[j]结尾,最长子数组的长度
2、dp[i][j]的递推关系:如果需要求以str1[i]和str2[j]结尾的最长子数组长度,则首先判断str1[i] 和str2[j]是否相等,如果不相等,则dp[i][j]为0,如果相等,则dp[i][j] = dp[i-1][j-1] + 1
代码编写
java语言版本
原问题:
递归方法:
/**
* 获取最长子数组
* @param str1
* @param str2
* @return
*/
public static String getMaxSubArrCP(String str1, String str2) {
if (str1 == null || str1.length() == 0
|| str2 == null || str2.length() == 0) {
return null;
}
char[] chars1 = str1.toCharArray();
char[] chars2 = str2.toCharArray();
int[][] dp = new int[chars1.length][chars2.length];
int[] maxIJ = getDpCP(chars1, chars2, dp);
// 将最大值的坐标拿出来
int maxI = maxIJ[0];
int maxJ = maxIJ[1];
int maxLen = chars1.length > chars2.length ? chars1.length : chars2.length;
int index = 0;
char[] res = new char[maxLen];
while (maxI >= 0 && maxJ >= 0) {
if (chars1[maxI] == chars2[maxJ]) {
res[index++] = chars1[maxI];
maxI--;
maxJ--;
}else {
break;
}
}
CommonUtils.reverseChar(res, 0, index);
return String.valueOf(res, 0, index);
}
/**
* 生成dp矩阵
* 返回最大值的两个坐标
* @param chars1
* @param chars2
* @return
*/
private static int[] getDpCP(char[] chars1, char[] chars2, int[][] dp) {
// dp[i][j] 表示,chars[i]为底和chars[2]为底的公共子数组长度,区别于chars1[i]为底的,chars2[j]为底的数组的公共子数组长度
//int[][] dp = new int[chars1.length][chars2.length];
int maxI = 0;
int maxJ = 0;
int max = Integer.MIN_VALUE;
dp[0][0] = chars1[0] == chars2[0] ? 1 : 0;
for (int i = 1; i < dp.length; i++) {
dp[i][0] = dp[i-1][0] == 1 || chars1[i] == chars2[0] ? 1 : 0;
}
for (int j = 1; j < dp[0].length; j ++) {
dp[0][j] = dp[0][j-1] == 0 || chars1[0] == chars2[j] ? 1 : 0;
}
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < dp[0].length; j++) {
if (chars1[i] != chars2[j]) {
dp[i][j] = 0;
}else {
int count = 1;
int iIndex = i;
int jIndex = j;
while (iIndex >= 0 && jIndex >= 0) {
if (chars1[iIndex] == chars2[jIndex]) {
count++;
iIndex--;
jIndex--;
}else {
break;
}
}
if (count > max) {
maxI = i;
maxJ = j;
max = count;
}
dp[i][j] = count;
}
}
}
return new int[]{maxI, maxJ};
}
/**
* 降低空间复杂度版本
* @param str1
* @param str2
* @return
*/
private static String getMaxSubArrCPReduceMem(String str1, String str2) {
if (str1 == null || str1.length() == 0
|| str2 == null || str2.length() == 0) {
return null;
}
char[] chars1 = str1.toCharArray();
char[] chars2 = str2.toCharArray();
int max = Integer.MIN_VALUE;
int maxI = 0;
int maxJ = 0;
int i = 0;
int j = chars2.length-1;
int count = chars1.length + chars2.length -1;
while (count-- >= 0) {
int temI = i;
int temj = j;
int temMax = 0;
int temMaxI = 0;
int temMaxJ = 0;
int last = 0;
while (temI < chars1.length && temj < chars2.length) {
if (chars1[temI] == chars2[temj]) {
last++;
}else {
last = 0;
}
if (last > temMax) {
temMax = last;
temMaxI = temI;
temMaxJ = temj;
}
temI++;
temj++;
}
if (temMax > max) {
maxI = temMaxI;
maxJ= temMaxJ;
max= temMax;
}
if (j != 0) {
// 还在第一行
j--;
}else {
i++;
}
}
// 将最大值的坐标拿出来
int maxLen = chars1.length > chars2.length ? chars1.length : chars2.length;
int index = 0;
char[] res = new char[maxLen];
while (maxI >= 0 && maxJ >= 0) {
if (chars1[maxI] == chars2[maxJ]) {
res[index++] = chars1[maxI];
maxI--;
maxJ--;
}else {
break;
}
}
CommonUtils.reverseChar(res, 0, index);
return String.valueOf(res, 0, index);
}
public static void main(String[] args) {
getMaxSubArrCPReduceMem("1AB2345CD", "12345EF");
}
c语言版本
正在学习中
c++语言版本
正在学习中
思考感悟
首先想要理解这道题,可以参考一下
https://swzhao.blog.csdn.net/article/details/127526166
只读感悟即可,如果我没有感悟上一道题,这道题是不会做的,首先上道题把规律应该讲的比较清楚,这道题也是一道最优解不是dp最后一个元素类型的问题,那么很显然,同样的感觉 以每一个元素为底时的结果有可能不包含该元素,这个时候就需要强制将当前元素变成底来做动态规划,当我想到这个思路的时候这道题基本上就是秒了。
这里提一句降低空间复杂度的版本,这个最优解为什么能够产生呢?是因为子数组都是连续的,不像子序列,并且子数组str1和str2元素都是相等的,所以这个最优解的代表仅仅只需要子数组的头或者尾就可以了,因此整个过程就是求最优解的头或者尾就行了。
写在最后
方案和代码仅提供学习和思考使用,切勿随意滥用!如有错误和不合理的地方,务必批评指正~
如果需要git源码可邮件给2260755767@qq.com
再次感谢左大神对我算法的指点迷津!
相关文章
- 五大常用算法之二:动态规划算法(DP)
- Java实现 LeetCode 740 删除与获得点数(递推 || 动态规划?打家劫舍Ⅳ)
- Java实现 LeetCode 1162 地图分析(可以暴力或者动态规划的BFS)
- 重新整理数据结构与算法(c#)—— 算法套路动态规划算法[二十六]
- 数据结构和算法—动态规划
- 【机组组合】基于Benders分解算法解决混合整数规划问题——机组组合问题(Matlab代码实现)
- 【路径规划】基于RRT算法和改进人工势场法的无人机任务规划方法研究(Python代码实现)
- 【无人机路径规划】基于IRM和RRTstar进行无人机路径规划(Matlab代码实现)
- 基于Dijkstra和A*算法的机器人路径规划(Matlab代码实现)
- 基于改进粒子群优化算法的UAV三维路径规划研究(Matlab代码实现)
- 【无人机】基于球向量的粒子群优化(SPSO)算法在无人机路径规划中的实现(Matlab代码实现)
- 聊聊不太符合常规思维的动态规划算法
- m基于自适应遗传优化的IEEE-6建设费用和网络损耗费用最小化电网规划算法matlab仿真
- 【LeetCode 简单 动态规划 python3】1025. 除数博弈
- 518. 零钱兑换 II-动态规划算法
- 剑指 Offer 63. 股票的最大利润-动态规划算法
- [LeetCode] 651. 四键键盘 ☆☆☆(动态规划)
- [LeetCode] 523. 连续的子数组和 ☆☆☆(动态规划)
- 【数学建模】8 非线性规划及例题讲解
- 解锁复杂问题的秘密武器:动态规划算法
- C++算法之动态规划实例
- 路径规划算法:RRT,RRT*,B-RRT*算法 - 附代码