Printing Shortest Common Supersequence in Java
Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If there are multiple valid strings, return any of them.
Example 1
Input: str1 = "abac", str2 = "cab"
Output: "cabac"
Explanation: str1 = "abac" is a subsequence of "cabac" because we can delete the first "c". str2 = "cab" is a subsequence of "cabac" because we can delete the last "ac".
Example 2
Input: str1 = "AGGTAB", str2 = "GXTXAYB"
Output: "AGXGTXAYB" or “AGGXTXAYB”
Explanation: str1 = "AGGTAB" is a subsequence of "AGXGTXAYB" because we can delete the "X" and "Y". str2 = "GXTXAYB" is a subsequence of "AGXGTXAYB" because we can delete the "A", "G", "G", and "T".
Approach 1: Using Dynamic programming
The Dynamic Programming (DP) approach for finding the Shortest Common Supersequence (SCS) of two strings. It involves constructing a 2D DP table that helps in building the SCS by considering the lengths of the shortest common supersequences of all prefixes of the given strings.
Algorithm
Step 1: Initialize the DP Table:
Step 1.1: Create a 2D array dp of size (m+1) x (n+1), where m is the length of string X and n is the length of string Y.
Step 1.2: dp[i][j] will store the length of the SCS of X[0...i-1] and Y[0...j-1].
Step 2: Fill the DP Table:
Step 2.1: If either string is empty, the SCS is the length of the other string.
Step 2.2: If the characters at the current position in both strings match, the length of the SCS is incremented by 1 from the diagonal value dp[i-1][j-1].
Step 2.3: If the characters do not match, the length of the SCS is 1 plus the minimum value from the cell above dp[i-1][j] or the cell to the left dp[i][j-1].
Step 3: Construct the SCS:
Step 3.1: Start from dp[m][n] and backtrack to build the SCS.
Step 3.2: If the characters match, include the character in the SCS and move diagonally.
Step 3.3: If the characters do not match, move in the direction of the smaller value (up or left).
Step 3.4: Append the remaining characters from either string if any are left.
FileName: ShortestCommonSupersequenceDP.java
public class ShortestCommonSupersequenceDP { // Function to find and print the SCS of two strings public static String printSCS(String X, String Y) { int m = X.length(); // Length of first string int n = Y.length(); // Length of second string int[][] dp = new int[m + 1][n + 1]; // DP table to store lengths of SCS // Fill dp array for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i == 0) { dp[i][j] = j; // If X is empty, SCS is Y up to j } else if (j == 0) { dp[i][j] = i; // If Y is empty, SCS is X up to i } else if (X.charAt(i - 1) == Y.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + 1; // Characters match, take diagonal value + 1 } else { dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1]); // Characters don't match, take min of left or top cell + 1 } } } // Build SCS from dp array int i = m, j = n; StringBuilder scs = new StringBuilder(); while (i > 0 && j > 0) { if (X.charAt(i - 1) == Y.charAt(j - 1)) { scs.append(X.charAt(i - 1)); // Characters match, add to SCS i--; j--; } else if (dp[i - 1][j] < dp[i][j - 1]) { scs.append(X.charAt(i - 1)); // Add character from X i--; } else { scs.append(Y.charAt(j - 1)); // Add character from Y j--; } } // Include remaining characters of X while (i > 0) { scs.append(X.charAt(i - 1)); i--; } // Include remaining characters of Y while (j > 0) { scs.append(Y.charAt(j - 1)); j--; } return scs.reverse().toString(); // Reverse the result since we built it backwards } public static void main (String[] args) { String X = "abac"; String Y = "cab"; System.out.println("Shortest Common Supersequence: " + printSCS(X, Y)); } }
Output
Shortest Common Supersequence: cabac
Time Complexity: The time complexity of an algorithm is O(m * n). Filling the DP table takes O(m * n) time because each cell in the table is computed in constant time and there are m * n cells.
Space Complexity: The space complexity is O(m * n) due to the 2D array used to store the lengths of the SCS for all prefixes of the given strings.