当前位置:网站首页>Violent recursion to dynamic programming 06 (the sword refers to Offer II 095. Longest common subsequence)
Violent recursion to dynamic programming 06 (the sword refers to Offer II 095. Longest common subsequence)
2022-08-03 02:33:00 【Taotao can't learn English】
1143.最长公共子序列
给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列的长度.
一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串.
例如,“ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列.两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列.
若这两个字符串没有公共子序列,则返回 0.
示例 1:
输入:text1 = “abcde”, text2 = “ace”
输出:3
解释:最长公共子序列是 “ace”,它的长度为 3.
示例 2:
输入:text1 = “abc”, text2 = “abc”
输出:3
解释:最长公共子序列是 “abc”,它的长度为 3.
示例 3:
输入:text1 = “abc”, text2 = “def”
输出:0
解释:两个字符串没有公共子序列,返回 0.
提示:
- 1 <= text1.length <= 1000
- 1 <= text2.length <= 1000
输入的字符串只含有小写英文字符.
暴力递归
I can't tell,Whoever said it, please say it in the comment area.
public int longestCommonSubsequence(String text1, String text2) {
return getLongLest(text1, text1.length() - 1, text2, text2.length() - 1);
}
private int getLongLest(String text1, int text1Index, String text2Str, int text2tIndex) {
if (text1Index == 0 && text2tIndex == 0) {
//Compares the current bits for equality
return text1.charAt(text1Index) == text2Str.charAt(text2tIndex) ? 1 : 0;
} else if (text1Index == 0) {
//When the left ends, the left does not move more than the right
return text1.charAt(text1Index) == text2Str.charAt(text2tIndex) ? 1 : getLongLest(text1, text1Index, text2Str, text2tIndex - 1);
} else if (text2tIndex == 0) {
//When the right side ends, the right side does not move more than the left side
return text1.charAt(text1Index) == text2Str.charAt(text2tIndex) ? 1 : getLongLest(text1, text1Index - 1, text2Str, text2tIndex);
} else {
//都不為0
int p1 = getLongLest(text1, text1Index, text2Str, text2tIndex - 1);
int p2 = getLongLest(text1, text1Index - 1, text2Str, text2tIndex);
//No end is more than the middle
int p3 = text1.charAt(text1Index) == text2Str.charAt(text2tIndex) ? 1 + getLongLest(text1, text1Index - 1, text2Str, text2tIndex - 1) : Integer.MIN_VALUE;
return Math.max(p1, Math.max(p2, p3));
}
}
动态规划
This is much better to say
Initialize the first bit first,相等则为1,否则为0,初始化第一行,用aCompare with each one,相等则为1,Otherwise, the previous number,Why for the previous number?Think for yourself,比如a和a比是1,那a和ab比呢,也是1啊.纵向也一样;
然后从ij1开始比,Because the two are compared to each other,If the current bits are not equal,Take the maximum value from the left and the top,If the current bits are equal,Also and top left + 1 Take the maximum value.That is, the current position is moved one position backward,Naturally use the number at that position + 1 了.
public int longestCommonSubsequence2(String text1, String text2) {
int m = text1.length();
int n = text2.length();
char[] s1 = text1.toCharArray();
char[] s2 = text2.toCharArray();
int[][] dp = new int[m][n];
//first initialization
dp[0][0] = s1[0] == s2[0] ? 1 : 0;
//Row and column initialization
for (int i = 1; i < m; i++) {
dp[i][0] = s1[i] == s2[0] ? 1 : dp[i - 1][0];
}
for (int i = 1; i < n; i++) {
dp[0][i] = s1[0] == s2[i] ? 1 : dp[0][i - 1];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
int left = dp[i][j - 1];
int up = dp[i - 1][j];
int cur = s1[i] == s2[j] ? 1 + dp[i - 1][j - 1] : 0;
dp[i][j] = Math.max(left, Math.max(up, cur));
}
}
return dp[m - 1][n - 1];
}
边栏推荐
猜你喜欢
随机推荐
async-await
Visual Studio中vim模拟器
【Leetcode】305.岛屿数量II(困难)
全栈---Proxy
v-if、v-else、v-elseif v-show v-for
牛客网剑指offer刷题练习之链表中环的入口结点
Qt在选择MSVC 编译器的时候,无法识别出M_PI的问题处理
记一次sql优化Using temporary; Using filesort
Greenplum数据库故障分析——can not listen port
Violence recursion to dynamic programming 08 (pony go chess)
DB2数据库-获取表结构异常:[jcc][t4][1065][12306][4.26.14]CharConvertionException ERRORCODE=-4220,SQLSTATE=null
基于rt-thread studio的STM32裸机开发——LED
Auto.js special positioning control method cannot perform blocking operations on the ui thread, please use setTimeout instead
【mysql知识点整理】--- order by 、group by 出现Using filesort原因详解
.NET深入解析LINQ框架(四:IQueryable、IQueryProvider接口详解)
淘宝商品销量接口/淘宝商品销量监控接口/商品累计销量接口代码对接分享
有奖提问|《新程序员》专访“Apache之父”Brian Behlendorf
德邦科技通过注册:年营收5.8亿 国家集成电路基金为大股东
吴恩达深度学习deeplearning.ai——第一门课:神经网络与深度学习——第一节:深度学习概论
鲲鹏devkit开发套件