对于两个字符串，请设计一个高效算法，求他们的最长公共子序列的长度，这里的最长公共子序列定义为有两个序列U1,U2,U3...Un和V1,V2,V3...Vn,其中Ui<Ui+1，Vi<Vi+1。且A[Ui] == B[Vi]。
给定两个字符串A和B，同时给定两个串的长度n和m，请返回最长公共子序列的长度。保证两串长度均小于等于300。
测试样例：
"1A2C3D4B56",10,"B1D23CA45B6A",12
返回：6
[编程题]最长公共子序列
import java.util.*;
public class LCS {
public int findLCS(String A, int n, String B, int m) {
// write code here
int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (A.charAt(i - 1) == B.charAt(j - 1)) {
dp[i][j] = Math.max(dp[i - 1][j - 1] + 1, dp[i][j]);
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[n][m];
}
}
发表于 2023-04-06 15:14:07
回复(0)
import java.util.*;
public class LCS {
public int findLCS(String A, int n, String B, int m) {
// write code here
int[][] dp = new int[n][m];
for (int i = 0; i < n; i++) {
String firstB = B.substring(0, 1);
String subA = A.substring(0, i + 1);
if (subA.contains(firstB)) {
dp[i][0] = 1;
}
}
for (int j = 0; j < m; j++) {
String firstA = A.substring(0, 1);
String subB = B.substring(0, j + 1);
if (subB.contains(firstA)) {
dp[0][j] = 1;
}
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
int a = dp[i - 1][j];
int b = dp[i][j - 1];
if (A.charAt(i) == B.charAt(j)) {
int c = dp[i - 1][j - 1] + 1;
dp[i][j] = Math.max(Math.max(a, b), c);
} else {
dp[i][j] = Math.max(a, b);
}
}
}
return dp[n - 1][m - 1];
}
}
public class LCS {
public int findLCS(String A, int n, String B, int m) {
// write code here
int[][] dp = new int[n][m];
for (int i = 0; i < n; i++) {
String firstB = B.substring(0, 1);
String subA = A.substring(0, i + 1);
if (subA.contains(firstB)) {
dp[i][0] = 1;
}
}
for (int j = 0; j < m; j++) {
String firstA = A.substring(0, 1);
String subB = B.substring(0, j + 1);
if (subB.contains(firstA)) {
dp[0][j] = 1;
}
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
int a = dp[i - 1][j];
int b = dp[i][j - 1];
if (A.charAt(i) == B.charAt(j)) {
int c = dp[i - 1][j - 1] + 1;
dp[i][j] = Math.max(Math.max(a, b), c);
} else {
dp[i][j] = Math.max(a, b);
}
}
}
return dp[n - 1][m - 1];
}
}
发表于 2018-06-10 19:04:56
回复(0)
import java.util.*;
public class LCS {
public int findLCS(String A, int n, String B, int m) {
int[][] dp = new int[n+1][m+1];
int max = 0;
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
if(A.charAt(i-1) == B.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] + 1;
if(dp[i][j] > max) max = dp[i][j];
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
return max;
}
}
发表于 2018-03-19 16:13:31
回复(0)
dp[i][j] 表示str1 前i个字符和 str2 前j 个字符的最长公共子序列的长度
public static int getLongestCommonSubsequence(String str1,String str2){
int len1=str1.length(),len2=str2.length();
int[][] dp=new int[len1][len2];
for(int i=0;i<len1;i++)
for(int j=0;j<len2;j++){
if(str1.charAt(i) == str2.charAt(j)){
if(i==0 || j==0)
dp[i][j] = 1;
else
dp[i][j]=dp[i-1][j-1]+1;
}
else{
if(i==0 || j==0)
dp[i][j] = 0;
else
dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[len1-1][len2-1];
}
编辑于 2017-08-09 15:17:18
回复(0)
import java.util.*;
public class LCS {
public static int findLCS(String A, int n, String B, int m) {
// write code here
int dp[][] = new int[n+1][m+1];
for(int i = 0 ; i < n ; i ++){
for(int j = 0 ; j < m ; j ++){
if(A.charAt(i) == B.charAt(j)){
dp[i+1][j+1] = dp[i][j]+1;
}else {
dp[i+1][j+1] = Math.max(dp[i][j+1], dp[i+1][j]);
}
}
}
return dp[n][m];
}
}
发表于 2017-08-01 14:19:28
回复(0)
//第一次做这个题，不过看思路懂了。自己也做出来了
/*
0 1 2 3 4 5 j
i0
1
2
3
4
i=j=0时，dp[i][j]=0
A[i]=B[j]时(从1计数)，dp[i][j]=dp[i-1][j-1]+1
A[i]!=B[j]时，dp[i][j]=max(dp[i][j-1],dp[i-1][j])
*/
import java.util.*;
public class LCS {
public int findLCS(String A, int n, String B, int m) {
// 行对应A，比A长1，原因是0作为初始化。列同理。dp[n][m]指A[n-1],B[m-1]
int[][] dp = new int[n+1][m+1];
for(int i=0;i<dp.length;i++){
dp[i][0]=0;
}
for(int i=0;i<dp[0].length;i++){
dp[0][i]=0;
}
//事实上，数组默认也是0
for(int i=1;i<dp.length;i++){
for(int j=1;j<dp[0].length;j++){
//如果是字符串，用equals，由于charAt()是字符，可以运算，故可以用==
if(A.charAt(i-1)==B.charAt(j-1)){//A[0]==B[0],对应dp[1][1]
dp[i][j]=dp[i-1][j-1]+1;
}else{
dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]);
}
}
}
return dp[n][m];
}
}
发表于 2017-03-15 20:35:10
回复(0)
import java.util.*;
public class LCS {
public int findLCS(String A, int n, String B, int m) {
int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i < n + 1; i ++ ) {
for (int j = 1; j < m + 1; j ++ ) {
if(A.charAt(i - 1) == B.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[n][m];
}
}
发表于 2016-10-18 10:58:45
回复(0)
import java.util.*;
public class LCS {
public int findLCS(String A, int n, String B, int m) {
// write code here
char[] a = A.toCharArray();
char[] b = B.toCharArray();
int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (a[i - 1] == b[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[n][m];
}
}
发表于 2016-08-30 00:58:06
回复(1)
问题信息
通过挑战的用户
查看代码-
2022-10-28 17:43:50
-
2022-09-14 18:56:42 -
2022-09-13 16:08:48
-
2022-09-01 22:18:56
-
2022-08-27 18:35:50
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
class LCS { public: int findLCS(string A, int n, string B, int m) { // write code here int table[n + 1][m + 1]; for(int i = 0;i <= n;++i)table[i][0] = 0; for(int i = 0;i <= m;++i)table[0][i] = 0; for(int i = 0;i < n;++i){ for(int j = 0;j < m;++j){ if(A[i] == B[j]) table[i + 1][j + 1] = table[i][j] + 1; else { table[i + 1][j + 1] = max(table[i][j + 1],table[i + 1][j]); } } } return table[n][m]; } };