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.
A string s is a subsequence of string t if deleting some number of characters from t (possibly 0) results in the string s.
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". The answer provided is the shortest such string that satisfies these properties.
Example 2:
Input: str1 = "aaaaaaaa", str2 = "aaaaaaaa" Output: "aaaaaaaa"
Constraints:
1 <= str1.length, str2.length <= 1000str1 and str2 consist of lowercase English letters.This approach involves creating a dynamic programming table to calculate the Longest Common Subsequence (LCS) between the two strings. The shortest common supersequence will be constructed based on the LCS. We iterate through both strings and build a table where each cell represents the length of the LCS of the substrings up to given indices. After filling the table, we backtrack from the bottom-right cell to find the LCS, which helps in forming the shortest common supersequence by adding remaining characters from both strings.
In this Python implementation, we first compute the LCS using a dynamic programming table. Starting from the bottom-right corner, we backtrack to build the shortest common supersequence (SCS) by comparing characters in str1 and str2. Each matched character in both strings appends to the SCS, and unmatched characters are appended based on the higher value in the DP table, ensuring the constructed SCS is minimal.
Java
Time Complexity: O(m * n), where m and n are the lengths of str1 and str2. This is due to filling the DP table.
Space Complexity: O(m * n) for the DP table.
This approach leverages a two-pointer strategy to iterate through both strings simultaneously. We will construct the shortest common supersequence by greedily adding characters while moving through str1 and str2 step by step. This method emphasizes adding each character when they mismatch and consolidating the sequence when they match.
This C implementation uses two indices to traverse both strings. As the iteration proceeds, characters from str1 and str2 are added to the result array unless they match, in which case, the common character is added once. This greedy manner yields the shortest common supersequence.
JavaScript
Time Complexity: O(m + n) where m and n are the lengths of str1 and str2. We iterate across both strings once.
Space Complexity: O(m + n) for storing the result string.
| Approach | Complexity |
|---|---|
| Dynamic Programming to Find LCS | Time Complexity: |
| Iterative Greedy Approach | Time Complexity: |
DP 31. Shortest Common Supersequence | DP on Strings • take U forward • 199,680 views views
Watch 9 more video solutions →Practice Shortest Common Supersequence with our built-in code editor and test cases.
Practice on FleetCode