第四天:《LeetCode一天一例》-----寻找最长公共子序列LCS(python实现)
最长公共子序列
题目:什么是公共子序列?假设,有一个串:‘我是个好人’, 还有一个串:‘我朋友是个好人’。 这两个串都有子串‘我是好’,这里的子串并不是非要连续,但是它要遵循主串中各个元素出现的先后顺序。。例如:"我" 在 “是” 的前面, "好” 在 “是” 的后面。。寻找最长公共子序列可以用于对比两个字符串的相似度。 公共子串越长,说明相似度越高呀。。
给个栗子: x串: ‘ABCBDAB’。 y串:‘BDCABA’ 我们要找出其最长公共子串。
解析: 采用动态规划的思想:
直接给出式子? 这不是要人命呀? 听我娓娓道来
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位置的长度长?
下面我们针对上述栗子给出手工求解的过程:
那里面的箭头是为了方便输出公共子序列。 里面的数字代表在当前位置 公共串的长度。 箭头的方向是你计算当前值依赖的是前一个方向的哪个值。
怎样输出公共子串? 记住 箭头是斜着 “左上” 代表当前位置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)
输出结果: