Algorithms for Coding Interviews in Python/

...

/

Solution: Shortest Common Supersequence(SCS)

Solution: Shortest Common Supersequence(SCS)

This review provides a detailed analysis of the different ways to solve the shortest common supersequence problem.

We'll cover the following...

Solution 1: brute force

def shortest_common_supersequence_recursive(s1, s2, i1, i2):
    """
    Finds a shortest common super sequence length
    :param s1: First string
    :param s2: Second string
    :param i1: Starting index of substring
    :param i2: Ending index of substring
    :return: Length of shortest common superstring
    """
    if i1 == len(s1):
        return len(s2) - i2
    if i2 == len(s2):
        return len(s1) - i1
    if s1[i1] == s2[i2]:
        return 1 + shortest_common_supersequence_recursive(s1, s2, i1 + 1, i2 + 1)
    length1 = 1 + shortest_common_supersequence_recursive(s1, s2, i1, i2 + 1)
    length2 = 1 + shortest_common_supersequence_recursive(s1, s2, i1 + 1, i2)
    return min(length1, length2)
def shortest_common_supersequence(s1, s2):
    """
    Finds a shortest common super sequence length
    :param s1: First string
    :param s2: Second string
    :return: Length of shortest common superstring
    """
    return shortest_common_supersequence_recursive(s1, s2, 0, 0)
# Driver code to test the above function
if __name__ == '__main__':
    
    print(shortest_common_supersequence("abcdz", "bdcf"))
    print(shortest_common_supersequence("educative", "educative.io"))

Explanation

In this solution, we try all the superstrings–one character at a time.

  • If the sequences have a matching ith character, skip one character from both the sequences and make a recursive call for the remaining lengths (line 16 - line 17)
  • If the characters don’t match, call the function recursively twice by skipping one character from each string (line 19 - line 20)
  • Return the minimum result of these two calls (line 22)

Time complexity

The time complexity of the above algorithm is exponential O(2n+m)O(2^{n+m}), where n and m are ...