Print Shortest Common Super-sequence (SCS)

The Memoization Technique is basically an extension to the recursive approach so that we can overcome the problem of calculating redundant cases and thus decrease time complexity.

We can see that in each recursive call only the value of "n" and "m" (length) changes, so we can store and reuse the result of a function(..n, m..) call using a "n * m" 2-D array.

The 2-D array will store a particular state (n, m) if we get it the first time.

Now, if we come across the same state (n, m) again, instead of calculating it in exponential complexity, we can directly return its result stored in the table in constant time.

The time complexity of this solution is (n * m).

In addition, O(n * m) auxiliary space was used by the table.

This problem is a variation of the Shortest Common Super-sequence (SCS).

The idea is to generate all super-sequences of both given sequences and print the shortest among them.

Start from the last elements (n-1, m-1) of both subsequences:

If s1[n-1] == s2[m-1], this character will be common to both subsequences, so add it to the current super-sequence and check for the remaining (0...n-2, 0...m-2) characters.

If s1[n-1] != s2[m-1], then check recursively for (0...n-2, 0...m-1) and (0...n-1, 0...m-2) and return [s1.charAt(n - 1) or s2.charAt(m - 1)] + shortest sequence of these two. This +1 character is to consider non-matching character of non-picked sequence.

If any of the subsequences is exhausted (m ==0 or n ==0), add remaining characters of the other sequence to the super-sequences. This is the base condition.

This solution is exponential O(2^(m+n)) in term of time complexity.

In addition, O(n) auxiliary stack space was used for the recursion stack.