algorithm-in-python/dynamicProgramming/lcs.py

54 lines
1.5 KiB
Python
Raw Permalink Normal View History

2018-10-02 21:24:06 +08:00
''' mbinary
#########################################################################
# File : lcs.py
# Author: mbinary
# Mail: zhuheqin1@gmail.com
2019-01-31 12:09:46 +08:00
# Blog: https://mbinary.xyz
2018-10-02 21:24:06 +08:00
# Github: https://github.com/mbinary
# Created Time: 2018-08-25 12:00
# Description:
#########################################################################
'''
2020-04-15 12:28:20 +08:00
def lcs(a, b):
2018-08-29 15:52:02 +08:00
'''time: O(mn); space: O(mn)'''
2020-04-15 12:28:20 +08:00
m, n = len(a), len(b)
2018-08-29 15:52:02 +08:00
board = [[[] for i in range(n+1)] for i in range(m+1)]
for i in range(m):
for j in range(n):
2020-04-15 12:28:20 +08:00
if a[i] == b[j]:
board[i+1][j+1] = board[i][j]+[a[i]]
2018-08-29 15:52:02 +08:00
elif len(board[i][j+1]) < len(board[i+1][j]):
board[i+1][j+1] = board[i+1][j]
2020-04-15 12:28:20 +08:00
else:
2018-08-29 15:52:02 +08:00
board[i+1][j+1] = board[i][1+j]
return board[m][n]
2020-04-15 12:28:20 +08:00
def lcs2(a, b):
2018-08-29 15:52:02 +08:00
'''time: O(mn); space: O(m)'''
2020-04-15 12:28:20 +08:00
m, n = len(a), len(b)
2018-08-29 15:52:02 +08:00
board = [[] for i in range(n+1)]
for i in range(m):
upperLevel = board[0].copy()
2018-08-29 15:52:02 +08:00
for j in range(n):
tmp = board[j+1].copy()
2020-04-15 12:28:20 +08:00
if a[i] == b[j]:
board[j+1] = upperLevel+[a[i]]
elif len(board[j+1]) < len(board[j]):
2020-04-15 12:28:20 +08:00
board[j+1] = board[j].copy() # copy is needed
upperLevel = tmp
2018-08-29 15:52:02 +08:00
return board[n]
2020-04-15 12:28:20 +08:00
if __name__ == '__main__':
a = 'ABCBDAB'
b = 'BDCABA'
2020-04-15 12:28:20 +08:00
print('s1:', a)
print('s2:', b)
while 1:
2020-04-15 12:28:20 +08:00
print('lcs:', lcs2(a, b))
a = input('s1: ')
b = input('s2: ')