最长公共子序列

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

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

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)