第四天：《LeetCode一天一例》-----寻找最长公共子序列LCS（python实现）

朴灿烈づ我的快乐病毒、 2022-03-09 14:28 181阅读 0赞

# 最长公共子序列 #

>         题目：什么是公共子序列？假设，有一个串：**‘我是个好人**’， 还有一个串：‘**我朋友是个好人’**。 这两个串都有子串**‘我是好’，**这里的子串并不是非要连续，但是它要遵循主串中各个元素出现的先后顺序。。例如："我" 在 “是”  的前面， "好” 在 “是” 的后面。。寻找最长公共子序列可以用于对比两个字符串的相似度。 公共子串越长，说明相似度越高呀。。

***给个栗子： x串： ‘ABCBDAB’。 y串：‘BDCABA’  我们要找出其最长公共子串**。*

** **

**         解析：**  采用动态规划的思想：

![20190313133807935.png][]

直接给出式子？ 这不是要人命呀？  听我娓娓道来

c\[i\]\[j\] 代表：当考虑x串的第i个位置，y串的第j个位置时，我们最长公共子串的长度。 还有一点需注意：此处的i始终在x串上滑动，j 始终在y串滑动

***下面介绍各种情况：***

**情况1：** i =0 或者 j = 0： ①表示考虑x的第零个位置和y串的公共子串时： 肯定长度为0（因为x没有元素）

②或者表示考虑y串的第零个位置和x串的公共子串时：肯定长度也是零（因为y没有元素）

**情况2：** i, j > 0 并且x\[i\] = y\[j\]： 如果x串的第i 个元素和 y串第j 个元素相等。那就是在x\[i -1\]\[j -1\]的最优结果上再加1 （动态规划一般都是存在最优子结构，即：当前的求解，依赖子问题的最优解）

**情况3：** i, j > 0 并且 x\[i\] != x\[j\] ：如果x串的第i 个元素和 y串第j 个元素不相等。 我们此时就得考虑当前的最优子串长度，肯定是越长越好。 既然你们不等，那我就看在这个比较之前，串x在i位置，串y在j-1位置的长度长，还是串x在i-1位置串y在j位置的长度长？

**下面我们针对上述栗子给出手工求解的过程：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXdyb2FkODg_size_16_color_FFFFFF_t_70][]

那里面的箭头是为了方便输出公共子序列。 里面的数字代表在当前位置 公共串的长度。  箭头的方向是你计算当前值依赖的是前一个方向的哪个值。

怎样输出公共子串？  记住 箭头是斜着 “左上” 代表当前位置x\[i\] = y\[j\]。 我们就是要从上述图表的最右端开始，以此跟着箭头走， 出现  “左上” 箭头， 将x\[i\] 或者 y\[j\] 添加到列表中，最后将列表逆转，就是我们最后的公共子串。

**代码实现：**

def find_common_str(x, y):
    
        # 首先构造那个矩阵
        c = [[0 for i in range(len(y)+1)] for j in range(len(x)+1)]
    
        # 这里还得构造个矩阵，为了输出公共子序列
        singal = [[' ' for i in range(len(y))] for j in range(len(x))]
    
        for i in range(len(c)):
            for j in range(len(c[1])):
                if i == 0 or j == 0:
                    c[i][j] = 0
                elif x[i-1] == y[j-1]:
                    c[i][j] = c[i-1][j-1] + 1
                    singal[i-1][j-1] = '左上'
                else:
                    c[i][j] = max(c[i-1][j], c[i][j-1])
                    if c[i][j] == c[i-1][j]:
                        singal[i-1][j-1] = '向上'
                    else:
                        singal[i-1][j-1] = '向左'
    
        return c, singal
    
    def show(singal, x, y):
        common_str = []
        i = len(x)-1
        j = len(y)-1
        while i > 0 or j > 0:
            if singal[i][j] == "向上":
                i -= 1
            elif singal[i][j] == '向左':
                j -= 1
            else:
                common_str.append(x[i])
                # 这里添加为y[j] 也可以
                i -= 1
                j -= 1
        common_str = list(reversed(common_str))   # 将列表进行逆转
    
        return common_str
    
    
    
    if __name__ == '__main__':
        x = ['A', 'B', 'C', 'B', 'D', 'A', 'B']
        y = ['B', 'D', 'C', 'A', 'B', 'A']
    
        c, singal = find_common_str(x, y)
        for item in c:
            # 打印出我们所谓的那个矩阵
            print(item)
        for s in singal:
            print(s)
    
        # 找公共子序列
        common_str = show(singal, x, y)
    
        print("最大公共子序列:\n", common_str)

**输出结果：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXdyb2FkODg_size_16_color_FFFFFF_t_70 1][]

[20190313133807935.png]: /images/20220309/a90dc49349e84f7eb2138e2e0f31d500.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXdyb2FkODg_size_16_color_FFFFFF_t_70]: /images/20220309/38cc4248b88d454c8fb0bf22238e2d13.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXdyb2FkODg_size_16_color_FFFFFF_t_70 1]: /images/20220309/899e3107126646b3b5cc37cc39a5dd31.png