So I implemented the LCS algorithm once using a 2-D matrix to store values while the other one used a python dictionary. I found the dictionary implementation was easier to implement and was a more natural and intuitive way of solving the problem.
I just wanted to make sure if it's a correct way of implementing the LCS algorithm and how can I improve on it.
Using 2-D matrix
def LowestCommonSubstring(s1, s2):
LCS = [[0 for x in range(len(s2) + 1)] for x in range(len(s1) + 1)]
for i in range(1, len(s1)+1):
for j in range(1, len(s2)+1):
if s1[i - 1] == s2[j - 1]:
LCS[i][j] = 1 + LCS[i-1][j-1]
else:
LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])
return LCS[i][j]
using dictionary
cache = {}
def lcs(s1, s2):
global cache
if len(s1) == 0 or len(s2) == 0:
return 0
if (s1, s2) in cache:
return cache[(s1, s2)]
else:
if s1[-1] == s2[-1]:
cache[(s1, s2)] = 1 + lcs(s1[:-1], s2[:-1])
else:
cache[(s1, s2)] = max(lcs(s1[:-1], s2), lcs(s1, s2[:-1]))
return cache[(s1, s2)]
https://en.wikipedia.org/wiki/Longest_common_subsequence_problemThis this is the problem I'm trying to implement and for now my solution only calculates the length of the longest common substring.
