首页 > 试题广场 >

最长公共子序列

[编程题]最长公共子序列
  • 热度指数：13492 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

对于两个字符串，请设计一个高效算法，求他们的最长公共子序列的长度，这里的最长公共子序列定义为有两个序列U1,U2,U3...Un和V1,V2,V3...Vn,其中Ui&ltUi+1，Vi&ltVi+1。且A[Ui] == B[Vi]。

给定两个字符串A和B，同时给定两个串的长度n和m，请返回最长公共子序列的长度。保证两串长度均小于等于300。

测试样例：
"1A2C3D4B56",10,"B1D23CA45B6A",12
返回：6
算法知识视频讲解
查看答案及解析
添加回答
推荐
wudan3551头像 wudan3551
解题报告：
    这是经典的动态规划题目，定义子问题table[ i ][ j ]为字符串A的第一个字符到第 i 个字符串和字符串B的第一个字符串到第 j 个字符串的最长公共子序列，如A为“app”,B为“apple”，table[ 2 ][ 3 ]表示 “ap” 和 “app” 的最长公共字串。注意到代码中 table 的大小为 (n + 1) x (m + 1) ，这多出来的一行和一列是第 0 行和第 0 列，初始化为 0，表示空字符串和另一字符串的子串的最长公共子序列，例如table[ 0 ][ 3 ]表示 “” 和 “app” 的最长公共字串。
    当我们要求table[ i ][ j ]，我们要先判断A[ i ]和B[ j ]是否相同，如果相同他就是table[ i - 1 ][ j - 1 ] + 1，相当于在两个字符串都去掉一个字符时的最长公共字串再加 1；否则最长公共字串取table[ i ][ j - 1 ] 和table[ i - 1 ][ j ] 中大者。如下图： 

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];
    }
};

编辑于 2015-08-18 09:32:02 回复(6)
Java
阿里巴巴本地生活内推头像 阿里巴巴本地生活内推 
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)
Java
已注销头像 已注销
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];
    }
}
发表于 2018-06-10 19:04:56 回复(0)
Java
127.0.0.1头像 127.0.0.1

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)
Java
牛客2793674号头像 牛客2793674号 
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)
Java
_Arlene__头像 _Arlene__ 
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)
Java
王小叶头像 王小叶 
//第一次做这个题，不过看思路懂了。自己也做出来了
/*
	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)
Java
詆調壹點头像 詆調壹點 
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)
Java
JustYoung头像 JustYoung 
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)
提交观点

问题信息

贪心 动态规划
来自：面试常考算法题(九)-...
难度：
8条回答 34260浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最长公共子序列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号