首页 > 试题广场 > 最长公共子序列
[编程题]最长公共子序列
  • 热度指数:12675 时间限制: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]。

给定两个字符串AB,同时给定两个串的长度nm,请返回最长公共子序列的长度。保证两串长度均小于等于300。

测试样例:
"1A2C3D4B56",10,"B1D23CA45B6A",12
返回:6
推荐
解题报告:
    这是经典的动态规划题目,定义子问题table[ i ][ j ]为字符串A的第一个字符到第 i 个字符串和字符串B的第一个字符串到第 j 个字符串的最长公共子序列,如A“app”,B“apple”table[ 2 ][ 3 ]表示 “ap” 和 “app” 的最长公共字串。注意到代码中 table 的大小为 (n + 1) x (m + 1) ,这多出来的一行和一列是第 行和第 列,初始化为 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)
最近帮师兄做各公司的笔试题,各种动态规划。
所以来复习一下
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)
//第一次做这个题,不过看思路懂了。自己也做出来了
/*
	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) {
        // 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)
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)
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 回复(4)
思路(参考程序员代码面是指南),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)

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)
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)
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)
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)
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)
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)
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)
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)
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)
# -*- coding:utf-8 -*-
class LCS:
    def findLCS(self, A, n, B, m):
        #定义子问题dp[ i ][ j ]为字符串A的第一个字符到第 i 个字符串和字符串B的第一个字符串到第 j 个字符串的最长公共子序列
        dp=[[0 for i in range(m+1)]  for j in range(n+1)]
        for i in range(n):
            for j in range(m):
                #先判断A[ i ]和B[ j ]是否相同,如果相同就是dp[ i - 1 ][ j - 1 ] + 1,相当于在两个字符串都去掉一个字符时的最长公共字串再加 1
                if A[i]==B[j]:
                    dp[i+1][j+1]=dp[i][j]+1
                else:#不相同则最长公共字串取dp[ i ][ j - 1 ] 和dp[ i - 1 ][ j ] 中大者
                    dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
        return dp[n][m]

发表于 2018-08-13 14:51:26 回复(0)
//时间复杂度O(mn),空间复杂度O(m)
int findLCS(string A, int n, string B, int m) {
        // write code here
        if(n == 0 || m == 0)
            return 0;
        //空间复杂度优化O(m)
        vector<vector<int>> result(2, vector<int>(m+1,0));
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++){
                if(A[i-1] == B[j-1])
                    result[i%2][j] = result[(i-1)%2][j-1] + 1;
                else
                    result[i%2][j] = max(result[(i-1)%2][j], result[i%2][j-1]);
            }
        return result[n%2][m];
    }

发表于 2018-08-10 15:11:39 回复(0)

问题信息

难度:
60条回答 28043浏览

热门推荐

通过挑战的用户

查看代码