Hi, I wrote the following algorithm to figure out the Shortest Common Supersequence. It’s failing a couple of test cases e.g. s1 = “EducativeIsFun” and s2 = “AlgorithmsAreFun”. Not sure where I went wrong - would appreciate some feedback. Thanks.
def shortest_common_supersequence(s1, s2):
“”"
Finds the shortest common super sequence length
:param s1: First string
:param s2: Second string
:return: Length of shortest common superstring
“”"
# Write your code here!
table = {}
for c in s1:
if not (c in table):
table[c] = [0 for x in range(2)]
value = table[c]
value[0] = value[0] + 1
for c in s2:
if not (c in table):
table[c] = [0 for x in range(2)]
value = table[c]
value[1] = value[1] + 1
result = 0
for key in table:
value = table[key]
result += max(value[0], value[1])
return result