Problem Link: https://leetcode.com/problems/shortest-common-supersequence/
Hello! Today we’ll be looking at another variation of LCS which is to find the shortest common super sequence (SCS). Recall that a subsequence is a sequence of characters which could be formed by removing somecharacters from the original string. On the other hand, a supersequence is a sequence of characters which could be formed by adding some characters to the original string. For example, a possible supersequence of “abc” is “xaybzcxyz”.
As we want to find the shortest common supersequence of two strings, we must use all characters present in both strings. However, notice that we want to make it shortest so we dont’ have to use the repeating characters more than once.
s1 = “abc”
s2 = “bce”
SCS = “abce”
In this example, there is need to use “bc” twice like “abcbce”. In other words, we want to use the “LCS” only once. Therefore, we first find the LCS and then find the SCS. Below is the code,
Time Complexity: O(n²)
![[Leetcode] #1008 Construct Binary Search Tree from Preorder Traversal(C++/Tree/Medium)](https://miro.medium.com/v2/resize:fit:679/1*I4RG2CAiBIgoq31AVqJV2Q.jpeg)
![[Algorithm] Leetcode #91 Decode Ways (DP/Medium/C++) — How to solve ANY DP](https://miro.medium.com/v2/resize:fit:679/1*Dl0F36mQqB_LNtA_dKd3ug.jpeg)
![[Algorithm] Longest Common Substring (C++/DP/Medium)](https://miro.medium.com/v2/resize:fit:679/1*yuVzMhCJyDENbyhwAsrkwA.png)
