第四天:《LeetCode一天一例》-----寻找最长公共子序列LCS(python实现)

最长公共子序列

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

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

 

         解析:  采用动态规划的思想:

第四天:《LeetCode一天一例》-----寻找最长公共子序列LCS(python实现)

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

             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位置的长度长?

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

第四天:《LeetCode一天一例》-----寻找最长公共子序列LCS(python实现)

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

        怎样输出公共子串?  记住 箭头是斜着 “左上” 代表当前位置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)

输出结果:

第四天:《LeetCode一天一例》-----寻找最长公共子序列LCS(python实现)