Blog

Introduction:

Discover the magic of combining two strings seamlessly as we unravel the mystery of the “Shortest Common Supersequence.” In the realm of coding, this quest involves finding the shortest path to unite characters, creating a unique and compact supersequence.

Problem Statement:

Finding the Shortest Common Supersequence

You are given two strings, X and Y, both consisting of uppercase and lowercase letters. The lengths of X and Y are denoted by m and n, respectively. Your task is to determine the length of the smallest string that serves as a supersequence for both X and Y.

A supersequence is a string that has both X and Y as subsequences. In other words, it must contain all the characters of both strings in the same order as they appear in the original strings.

Example 1:

Input:

X = "abcd", Y = "xycd"

Output:

6

Explanation: The shortest common supersequence is “abxycd” with a length of 6, incorporating both strings as subsequences.

Example 2:

Input:

X = "efgh", Y = "jghi"

Output:

6

Explanation: The shortest common supersequence is “ejfghi” with a length of 6, encompassing both strings as subsequences.

Your Task:

You are required to implement the function shortestCommonSupersequence(X, Y, m, n) that takes X and Y as input strings along with their respective lengths (m and n) and returns the length of the shortest common supersequence.

Constraints:

• 1 <= |X|, |Y| <= 100

Expected Complexity:

• Time Complexity: O(Length(X) * Length(Y))
• Auxiliary Space: O(Length(X) * Length(Y))

How To Approach the Above Problem

1. Set Up a Table: Start by making a table with rows for the characters in X and columns for the characters in Y. Call it dp.
2. Handle Base Cases: Fill in the first row and column. If one string is empty, the supersequence’s length is just the length of the other string.
3. Go Through the Table: For each cell in the table (except the first row and column):
   • If the characters in X and Y match at that position, put one plus the diagonal cell’s value in the current cell.
   • If the characters don’t match, put one plus the minimum value from the cell above or the cell to the left.
4. Find the Result: Look at the last cell in the table (bottom-right). The number there is the length of the shortest common supersequence.

Solution (python) Geeks For Geeks

class Solution:
    
    # Function to find length of the shortest common supersequence of two strings.
    def shortestCommonSupersequence(self, X, Y, m, n):
        # Creating a 2D table to store the results of subproblems.
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        # Filling the table using bottom-up dynamic programming.
        for i in range(m + 1):
            for j in range(n + 1):
                if i == 0 or j == 0:
                    dp[i][j] = i + j
                elif X[i - 1] == Y[j - 1]:
                    dp[i][j] = 1 + dp[i - 1][j - 1]
                else:
                    dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1])
        
        # The length of the shortest common supersequence is given by:
        # length(X) + length(Y) - length(LCS(X, Y))
        return dp[m][n]

Code Explanation

1. Setting up the Table:

   dp = [[0] * (n + 1) for _ in range(m + 1)]

We create a table named dp with dimensions (m + 1) by (n + 1). This table will help us store the results of subproblems as we solve them.

2. Filling the Table using Dynamic Programming:

   for i in range(m + 1):
       for j in range(n + 1):
           if i == 0 or j == 0:
               dp[i][j] = i + j
           elif X[i - 1] == Y[j - 1]:
               dp[i][j] = 1 + dp[i - 1][j - 1]
           else:
               dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1])

We iterate through each cell in the table. If either X or Y is empty (i = 0 or j = 0), we set the value in the cell to the sum of i and j. Otherwise, if the characters in X and Y match, we set the value to one plus the diagonal cell’s value. If they don’t match, we set the value to one plus the minimum of the cell above or the cell to the left.

3. Calculating the Result:

   return dp[m][n]

The final result is the value in the bottom-right cell of the table. This value represents the length of the shortest common supersequence.

In simpler terms, this code uses a table to efficiently find the length of the shortest common supersequence by considering characters in strings X and Y, whether they match or not. The final result is stored in the bottom-right cell of the table.

Conclusion:

In the realm of coding, our exploration into dynamic programming has unveiled an elegant solution for the “Shortest Common Supersequence.” By adeptly blending characters, we reach the length of the shortest common supersequence, nestled in the bottom-right cell of our table—a testament to the coding prowess in string manipulation. Happy coding on your quest for the shortest common supersequence!