最长公共子串(动态规划)
规划 动态 最长 公共 子串
2023-09-14 09:07:34 时间
描述
有两个字符串(可能包含空格),请找出其中最长的公共连续子串,输出其长度。(长度在1000以内)
例如:
输入:abcde bcd
输出:3
解析
1、把两个字符串分别以行和列组成一个二维矩阵。
2、比较二维矩阵中每个点对应行列字符中否相等,相等的话值设置为1,否则设置为0。
3、通过查找出值为1的最长对角线就能找到最长公共子串。
比如:str=acbcbcef,str2=abcbced,则str和str2的最长公共子串为bcbce,最长公共子串长度为5。
针对于上面的两个字符串我们可以得到的二维矩阵如下:
从上图可以看到,str1和str2共有5个公共子串,但最长的公共子串长度为5。
为了进一步优化算法的效率,我们可以再计算某个二维矩阵的值的时候顺便计算出来当前最长的公共子串的长度,即某个二维矩阵元素的值由record[i][j]=1演变为record[i][j]=1 +record[i-1][j-1],这样就避免了后续查找对角线长度的操作了。修改后的二维矩阵如下:
递推公式为:
当A[i] != B[j],dp[i][j] = 0
当A[i] == B[j],
若i = 0 || j == 0,dp[i][j] = 1
否则 dp[i][j] = dp[i - 1][j - 1] + 1
代码
暴力法
public int getLCS(String s, String s2) { if (s == null || t == null) { return 0; } int l1 = s.length(); int l2 = t.length(); int res = 0; for (int i = 0; i < l1; i++) { for (int j = 0; j < l2; j++) { int m = i; int k = j; int len = 0; while (m < l1 && k < l2 && s.charAt(m) == t.charAt(k)) { len++; m++; k++; } res = Math.max(res, len); } } return res; }
动态规划
public int getLCS(String s, String t) { if (s == null || t == null) { return 0; } int result = 0; int sLength = s.length(); int tLength = t.length(); int[][] dp = new int[sLength][tLength]; for (int i = 0; i < sLength; i++) { for (int k = 0; k < tLength; k++) { if (s.charAt(i) == t.charAt(k)) { if (i == 0 || k == 0) { dp[i][k] = 1; } else { dp[i][k] = dp[i - 1][k - 1] + 1; } result = Math.max(dp[i][k], result); } else { dp[i][k] = 0; } } } return result; }
简化一下递推公式:
当A[i] != B[j],dp[i][j] = 0
否则 dp[i][j] = dp[i - 1][j - 1] + 1
全部都归结为一个公式即可,二维数组默认值为0
public int getLCS(String s, String t) { if (s == null || t == null) { return 0; } int result = 0; int sLength = s.length(); int tLength = t.length(); int[][] dp = new int[sLength + 1][tLength + 1]; for (int i = 1; i <= sLength; i++) { for (int k = 1; k <= tLength; k++) { if (s.charAt(i - 1) == t.charAt(k - 1)) { dp[i][k] = dp[i - 1][k - 1] + 1; result = Math.max(dp[i][k], result); } } } // for (int i = 1; i <= sLength + 1; i++) { // for (int k = 1; k <= tLength + 1; k++) { // System.out.print(dp[i - 1][k - 1] + " "); // } // System.out.println(); // } return result; }
行、列都多一行,更适应公式。
相关文章
- Java实现 LeetCode 714 买卖股票的最佳时机含手续费(动态规划 || 迭代法)
- Java实现 LeetCode 718 最长重复子数组(动态规划)
- Java实现 LeetCode 718 最长重复子数组(动态规划)
- 五大常用算法之二:动态规划算法(DP)
- Leetcode学习计划之动态规划入门day6(152, 1567)
- 精品数学规划求解器:Gurobi Optimizer 10.0.1 Crack
- 基于蚁群算法的车辆路径规划问题的研究(Matlab代码实现)
- 多因素蚁群算法的移动机器人路径规划研究(Matlab代码实现)
- 【路径优化】基于改进的RRT算法的全局路径规划(Matlab代码实现)
- 数学建模学习(13):整数规划之混合整数线性规划问题详解,建议收藏慢慢看!
- 野生前端的数据结构练习(11)动态规划算法
- 基于SA模拟退火优化的TWVRP路径规划matlab仿真
- 通过金矿模型介绍动态规划
- 【LeetCode Python实现】300. 最长递增子序列(中等)动态规划
- 516. 最长回文子序列-动态规划算法
- 剑指 Offer II 104. 排列的数目-动态规划算法
- 1191. K 次串联后最大子数组之和-暴力动态规划,和优化算法
- 剑指 Offer II 095. 最长公共子序列-动态规划算法
- 264. 丑数 II -动态规划算法
- 【Python算法】实验7-变治技术及动态规划初步
- 【Pytorch】第 2 章 :马尔可夫决策过程和动态规划