educative.io

Educative

Question re algorithm

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