Shortest Common Supersequence - Leetcode Solution

The Shortest Common Supersequence problem on LeetCode is a dynamic programming problem that asks you to find the length of the shortest common supersequence of two given strings. A supersequence is defined as a string that contains both of the given strings as subsequences.

To solve this problem, you can use dynamic programming. The algorithm will make use of a matrix of size (n+1) x (m+1), where n and m are the lengths of the given strings. Matrix[i][j] denotes the length of the shortest common supersequence of the substrings of the first string up to i and the substrings of the second string up to j.

Here is the detailed solution:

1. Initialize the matrix with 0's. This is because if either of the strings is empty, the shortest common supersequence would be the other string itself, which has length equal to its own length.

2. Fill the matrix by iterating through the substrings of both the strings. The idea is that if the last character of both substrings matches, then the length of the shortest common supersequence would be one plus the length of the shortest common supersequence of the remaining substrings. Otherwise, we need to consider all possible ways to append the last character of both substrings to make a new supersequence, and choose the one that has the shortest length.

3. Once the matrix is filled, the length of the shortest common supersequence would be stored in Matrix[n][m], where n and m are the lengths of the given strings.

Here is the Python code for the same:

def shortestCommonSupersequence(str1: str, str2: str) -> int:
    # Initializations
    n, m = len(str1), len(str2)
    Matrix = [[0]*(m+1) for i in range(n+1)]

    # Fill the matrix
    for i in range(1, n+1):
        for j in range(1, m+1):
            if str1[i-1] == str2[j-1]:
                Matrix[i][j] = 1 + Matrix[i-1][j-1]
            else:
                Matrix[i][j] = 1 + min(Matrix[i-1][j], Matrix[i][j-1])

    # The length of the shortest common supersequence is stored in Matrix[n][m]
    return Matrix[n][m]

This solution has a time complexity of O(nm), and a space complexity of O(nm).

1