首页 > 试题广场 >

最长公共子序列

[编程题]最长公共子序列

热度指数：13187 时间限制：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

解题报告：

这是经典的动态规划题目，定义子问题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)

JacobGo！

最近帮师兄做各公司的笔试题，各种动态规划。

所以来复习一下

import java.util.*;

public class LCS {
    public int findLCS(String A, int n, String B, int m) {
        int len1=n,len2=m;
		 int[][] res=new int[len1+1][len2+1];
		 
		 for(int i=0;i<len1;i++){
			 for(int j=0;j<len2;j++){
				 int cur=0;
				 if(A.charAt(i)==B.charAt(j))
					 cur++;
				 
				 res[i+1][j+1]=maxNum(res[i][j]+cur,res[i][j+1],res[i+1][j]);

			 }
		 }
		 return res[len1][len2];
	 }
    /*
	 * 返回三者最大值
	 */
	private int maxNum(int i, int j, int k) {
		int max = i;
		max = j > max ? j : max;
		max = k > max ? k : max;
		return max;
	}
}

发表于 2017-09-11 11:15:24 回复(0)

Java

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)

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)

gloomy

import java.util.*;

public class LCS {
    public int findLCS(String A, int n, String B, int m) {
        return getIncrementSequence(A,B);
    }
    
    
  	public int getIncrementSequence(String A, String B) {
		int a_len = A.length();
		int b_len = B.length();
		int[][] dp = new int[a_len+1][b_len+1];
		int size = 0;
		for (int i = 1; i <= a_len; i++) {
			for (int j = 1; j <= b_len; j++) {
				if (A.charAt(i-1) == B.charAt(j-1)) {
				    dp[i][j] = dp[i - 1][j - 1] + 1;
					if (dp[i][j] > size) {
						size = dp[i][j];
					}
				} 
				else {
					dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
				}
			}
		}
		return size;
	}
    }

编辑于 2016-04-06 19:59:50 回复(0)

张永胜潮阳

public class LCS {
    public int findLCS(String A, int n, String B, int m) {
        // write code here
        char[] a = A.toCharArray(),b = B.toCharArray();
        int[][] dp = new int[n+1][m+1];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                dp[i+1][j+1]= a[i]==b[j]?dp[i][j]+1 : 
                               Math.max(dp[i][j+1],dp[i+1][j]);
            }
        }
        return dp[n][m];
    }
}

编辑于 2019-01-18 20:43:52 回复(0)

Python

TimeMac

def findLCS(self, A, n, B, m):
        #result[i][j]保存A前i个子串和B前j个子串的公共子序列
        result = [[0 for i in range(m+1)] for j in range(n+1)]
        for i in range(1,n+1):
            for j in range(1,m+1):
                result[i][j] = max(result[i-1][j],result[i][j-1]) #默认传承之前的公共子序列长度
                if A[i-1]==B[j-1]:
                    result[i][j] = result[i-1][j-1]+1 #等于子串都减一的公共子序列长度加一
        return result[-1][-1]

编辑于 2018-09-23 20:16:19 回复(3)

杰斯007

思路（参考程序员代码面是指南），DP表，dp[i]][j]代表A[0...i]与B[0...j]的最长公共子序列；
我们先求出第一行与第一列的DP值，然后在求里面的值，里面的值有三种情况：
1.来自dp[i-1][j];
2.来自dp[i][j-1];
3.A[i]==B[j]时为dp[i-1][j-1];  
我们求出这三者的最大值即可，用一个res来计算。最后返回即可。

class LCS 

{ public:
    int findLCS(string A, int n, string B, int m) {
        // write code here
        if (n == 0 || m == 0) return 0;
        return getdp(A,n,B,m);
        
    }
    private:
    int getdp(string arrA, int n, string arrB, int m)
    {
        int res=0;
        vector<vector<int> >dp(n, vector<int>(m, 0));
        dp[0][0]=(arrA[0]==arrB[0]?1:0);
        for (int i = 1; i<n; i++){
            dp[i][0]=max(dp[i-1][0],arrA[i]==arrB[0]?1:0);
        }
        for (int j = 1; j<m; j++){
            dp[0][j]=max(dp[0][j-1],arrA[0]==arrB[j]?1:0);
        }
        for (int i = 1; i<n; i++){
            for (int j = 1; j<m; j++){
                dp[i][j]=max( dp[i - 1][j] , dp[i][j-1]) ;
                res=max( res ,dp[i][j]);
                if (arrA[i] == arrB[j])
                {
                    dp[i][j]=max(dp[i][j] , dp[i - 1][j - 1] + 1);
                    res = max( res, dp[i][j]);
                }
            }
        }
        return res;
    }
};

发表于 2018-04-07 17:07:32 回复(0)

C/C++

nbgao

class LCS {
public:
    int findLCS(string A, int n, string B, int m) {
        int dp[n+1][m+1];
        
        for(int i=0;i<=n;i++)
            dp[i][0] = 0;
        for(int j=0;j<=m;j++)
            dp[0][j] = 0;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            {
                if(A[i] == B[j])
                    dp[i+1][j+1] = dp[i][j] + 1;
                else
                    dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1]);             }         return dp[n][m];
    }
};

发表于 2017-10-14 01:53:49 回复(0)

Java

_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

詆調壹點

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)

Alex-大伟

package alex.suda.dp;

import java.util.Scanner;

public class test2 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			int n = scanner.nextInt();
			String A = scanner.next();
			int m = scanner.nextInt();
			String B = scanner.next();
			System.out.print(findLCS(A, n, B, m));
		}
	}

	public static int findLCS(String A, int n, String B, int m) {
		// 设d[i][j]为字符串A的1~i位和B的1~j位的最大公共子序列的长度
		// 则d[i][j] = d[i-1][j-1] + 1， 如果A[i] = A[j]
		// 否则 d[i][j] = max{d[i-1][j],d[i][j-1]}
		int[][] d = new int[n + 1][m + 1];
		//初始化
		for (int i = 0; i <= n; i++) {
			d[i][0] = 0;
		}
		for (int j = 0; j <= m; j++) {
			d[0][j] = 0;
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (A.charAt(i-1) == B.charAt(j-1)) {
					d[i][j] = d[i - 1][j - 1] + 1;
				} else {
					d[i][j] = Math.max(d[i - 1][j], d[i][j - 1]);
				}
			}
		}
		return d[n][m];
	}
}

发表于 2016-10-05 21:57:44 回复(0)

穆晨

解题报告：

1.dp[i]][j]中表示的是A串中前i个数和B串中的前j个数的最大公共子序列长度。

2.当我们开始挑选A，B串的下一个时即确定dp[i+1][j+1]时，如果这两个相等，即A[i] == B[j]，那么就可以直接把这相等的字母加进去，即dp[i+1][j+1] = dp[i][j] + 1.

3.当我们开始挑选A，B串的下一个时即确定dp[i+1][j+1]时，如果这两个不相等，即A[i] ！= B[j]，那么最大公共子列和要么是取A[i]不取B[j],要么是不取A[i]取Bp[j]。即从dp[i+1][i],dp[i][j+1]中取一个最大的。

代码如下：

class LCS {
public:
    int findLCS(string A, int n, string B, int m) {
        // write code here
        int dp[305][305];
        memset(dp,0,sizeof(dp));
        for(int i = 0;i<n;i++)
            for(int j = 0;j<m;j++){
            	if(A[i] == B[j])
                    dp[i+1][j+1] = dp[i][j] + 1;
            	else
                    dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j]);
        	}
       return dp[n][m];	
    }
};

编辑于 2015-08-10 21:59:50 回复(0)

Echo001

int findLCS(string A, int n, string B, int m) {
        int len = 0;
        int **temp = new int*[n+1];
        for(int i=0; i<n+1; i++){
            temp[i] = new int[m+1];
            temp[i][0] = 0;
        }                 
        for(int j=0; j<m+1; j++){            
            temp[0][j] = 0;
        }

        for(int i=1; i<n+1; i++){
            for(int j=1; j<m+1; j++){               
                if(A.at(i-1) == B.at(j-1)){
                    temp[i][j] = temp[i-1][j-1] + 1;
                    len = len<temp[i][j]?temp[i][j]:len;
                }else{
                    temp[i][j] = temp[i][j-1]<temp[i-1][j]?temp[i-1][j]:temp[i][j-1];
                }
            }
        }

        return len; 
    }

发表于 2016-07-23 15:27:25 回复(0)

我就信ycy拿到offer就喝一鸣

import java.util.*;

public class LCS {
    public int findLCS(String A, int n, String B, int m) {
        // 先确定好长度大小的
        String small = A.length() <= B.length() ? A : B;
        String big = A.length() > B.length() ? A : B;
        // 动态滚动数组 -- 因为涉及到的dp在求得每一个dp[i][j]的时候是不分 
        
        int[] dp = new int[Math.min(n, m)];
        // 初始化动态滚动数组
        for(int i = 0; i < dp.length; ++i){
            dp[i] = (big.charAt(0) ==  small.charAt(i) || (i > 1 && dp[i-1] == 1)) ? 1 : 0;
        }
        // 滚动更新动态数组
         // need to record the preVal
        int preValRecord = 0; // the golbal val for this below
        int preValForRefreshDp = 0; // also the global value for this below
        for(int i = 1; i < big.length(); ++i){
            for( int j = 0; j < dp.length; ++j){
                // first to refresh the first column for the dp[][] -- mean to the dp[0]
                // need to record the preVal
                preValRecord = dp[j];
                if(j == 0){
                    dp[0] = (small.charAt(0) == big.charAt(i) || dp[0] == 1) ? 1 : 0;
                }else{
                    dp[j] =(big.charAt(i) != small.charAt(j)) ? Math.max(dp[j], dp[j-1]) : preValForRefreshDp+1;
                }
                preValForRefreshDp = preValRecord;
            }
        }
        return dp[dp.length-1];
    }
}

看到上面都是用的dp，并且二维的，那我就贴一个一维的滚动数组的优化吧，还是得益于左神的思想，当然要想时间再缩短的话，就像字符串的处理一下，变成char数组，毕竟数组的查找会更快嘛。这里我主要是展示思想，就直接用的string对象的charAt的方式

编辑于 2018-04-02 08:51:10 回复(0)

Java

CalvinCoder

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)

牛客79631828号

import java.util.*;

public class LCS {
    public int findLCS(String A, int n, String B, int m) {
        // write code here
        //dp[i][j]表示A里从0...i与B里从0...j的最长公共子序列长度
        int[][] dp = new int[n][m];
        //设置base case
        for (int i = 0; i < m; i++) {
            if (i > 0 && dp[0][i-1] == 1) {
                dp[0][i] = 1;
                continue;
            }
            if (B.charAt(i) == A.charAt(0))
                dp[0][i] = 1;
        }
        
        for (int i = 0; i < n; i++) {
            if (i > 0 && dp[i-1][0] == 1) {
                dp[i][0] = 1;
                continue;
            }
            if (A.charAt(i) == B.charAt(0))
                dp[i][0] = 1;
        }
        
        //若A的i位置 ！= B的j位置，则有取三种情况中最大值
        //否则=A的0...i-1位置 与 B的0...j-1位置上最长公共子序列 + 1.
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                dp[i][j] = Math.max(dp[i-1][j-1], Math.max(dp[i-1][j], dp[i][j-1]));
                if (A.charAt(i) == B.charAt(j))
                    dp[i][j] = dp[i-1][j-1]+1;
            }
        }
        
        return dp[n-1][m-1];
    }
}

发表于 2021-07-15 16:20:04 回复(0)

RichardLee0

class LCS {
public:
    int findLCS(string A, int n, string B, int m) {
        int c[n+1][m+1];
        int i,j;
        for(i=0;i<=n;i++) c[i][0]=0;
        for(j=1;j<=m;j++) c[0][j]=0;
        
        for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
                if(A[i-1]==B[j-1])
                    c[i][j] = c[i-1][j-1] + 1;
                else if(c[i-1][j]>=c[i][j-1])
                    c[i][j] = c[i-1][j];
                else 
                    c[i][j] = c[i][j-1];
            }
        }
        return c[n][m];
    }
};

发表于 2020-01-31 12:28:22 回复(0)

week_

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;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;
                }else{
                    dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
        return dp[n][m];
    }
}

发表于 2019-06-03 17:46:44 回复(0)

要暴富的肱二头肌很贪吃

动态规划的经典问题，这里不多说。只mark一个小tips：dp维度设置为[n+1][m+1]避免了dp设置为[n][m]时判断i，j是否都小于1还是某一个小于1，这样就可以直接通过初始化dp三个特殊值：

dp[0][0] = 0;
dp[1][0] = 0;
dp[0][1] = 0;
后面可以直接将dp分两种情况处理即可。
直接上代码：

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];
        dp[0][0] = 0;
        dp[1][0] = 0;
        dp[0][1] = 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;
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[n][m];
    }
}

发表于 2018-12-08 20:31:44 回复(0)

C/C++

猴子居士

class LCS {
public:
    int findLCS(string A, int n, string B, int m) {
        // write code here
        int table[n + 1][m + 1];
        memset(table, 0, sizeof(table));
        for(int i = 1;i <= n;++i){
            for(int j = 1;j <= m;++j){
                if(A[i-1] == B[j-1])
                    table[i][j] = table[i-1][j-1] + 1;
                else {
                    table[i][j] = max(table[i-1][j],table[i][j-1]);
                }
            }
        }
        return table[n][m];
    }
};

发表于 2018-08-20 22:14:01 回复(0)