Problem Explanation:

The problem asks to find the shortest common supersequence from two provided strings.

A supersequence is a sequence that contains all elements of another sequence, possibly with other elements interspersed.

For example, Let's have two strings:

str1 = "abac" str2 = "cab"

The supersequence will be "cabac" where both str1 and str2 are subsequences. Each of str1 and str2 can be obtained from "cabac" by deleting some characters without changing the order of remaining characters.

Approach:

The problem is a standard problem of finding the shortest common supersequence which can be solved by finding a longest common subsequence (LCS).

The algorithm used in the solution is dynamic programming. We start solving the problem by finding the longest common subsequence of both strings. This can be done by creating a 2D dp array.

The idea is to append chars that are not part of the LCS into the answer until we meet a char of the LCS.

At last, append the remaining characters of both strings into the answer string.

Python Solution:

1
2python
3class Solution:
4    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
5        m, n = len(str1), len(str2)
6        dp = [["" for _ in range(n+1)] for _ in range(m+1)]
7        
8        for i in range(m):
9            for j in range(n):
10                if str1[i] == str2[j]:
11                    dp[i+1][j+1] = dp[i][j] + str1[i]
12                else:
13                    dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1], key=len)
14        
15        ans = ""
16        i, j = m, n
17        while i > 0 and j > 0:
18            if str1[i-1] == str2[j-1]:
19                ans = str1[i-1] + ans
20                i -= 1
21                j -= 1
22            elif len(dp[i-1][j]) > len(dp[i][j-1]):
23                i -= 1
24            else:
25                j -= 1
26        
27        return dp[-1][-1] + str1[i:j] + str2[i:j]

Java Solution:

1
2java 
3class Solution {
4    public String shortestCommonSupersequence(String str1, String str2) {
5        int m = str1.length(), n = str2.length();
6        int[][] dp = new int[m + 1][n + 1];
7
8        for (int i = 1; i <= m; i++) {
9            for (int j = 1; j <= n; j++) {
10                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
11                    dp[i][j] = 1 + dp[i - 1][j - 1];
12                } 
13                else {
14                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
15                }
16            }
17        }
18
19        StringBuilder sb = new StringBuilder();
20        while (m > 0 && n > 0) {
21            if (str1.charAt(m - 1) == str2.charAt(n - 1)) {
22                sb.append(str1.charAt(m - 1));
23                m--;
24                n--;
25            } 
26            else if (dp[m - 1][n] > dp[m][n - 1]) {
27                sb.append(str1.charAt(--m));
28            } 
29            else {
30                sb.append(str2.charAt(--n));
31            }
32        }
33
34        while (m > 0) {
35            sb.append(str1.charAt(--m));
36        }
37
38        while (n > 0) {
39            sb.append(str2.charAt(--n));
40        }
41
42        return sb.reverse().toString();
43    }
44}

Javascript Solution:

1
2javascript
3var shortestCommonSupersequence = function(str1, str2) {
4    let m = str1.length, n = str2.length;
5    let dp = new Array(m+1).fill(0).map(x => new Array(n+1).fill(0));
6    for(let i=1;i<=m;i++){
7        for(let j=1;j<=n;j++){
8            if(str1[i-1] == str2[j-1]) dp[i][j] = 1+dp[i-1][j-1];
9            else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
10        }
11    }
12    let i=m,j=n,res = [];
13    while(i > 0 && j > 0){
14        if(str1[i-1] == str2[j-1]){
15            res.unshift(str1[--i]);
16            j--;
17        }
18        else if(dp[i-1][j] > dp[i][j-1]){
19            res.unshift(str1[--i]);
20        }
21        else{
22            res.unshift(str2[--j]);
23        }
24    }
25    while(i > 0) res.unshift(str1[--i]);
26    while(j > 0) res.unshift(str2[--j]);
27    return res.join('');
28};

C++ Solution:

1
2cpp
3class Solution {
4public:
5string shortestCommonSupersequence(string str1, string str2) {
6int n1=str1.length();
7int n2=str2.length();
8vector<vector<int>>dp(n1+1,vector<int>(n2+1,0));
9for(int i=1;i<=n1;i++)
10    for(int j=1;j<=n2;j++)
11        if(str1[i-1]==str2[j-1])
12            dp[i][j]=1+dp[i-1][j-1];
13        else
14            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
15string ans;
16int i=n1,j=n2;
17while(i>0 && j>0)
18{
19    if(str1[i-1]==str2[j-1])
20    {
21        ans=str1[i-1]+ans;
22        i--;
23        j--;
24    }
25    else if(dp[i-1][j]>dp[i][j-1])
26    {
27        ans=str1[i-1]+ans;
28        i--;
29    }
30    else
31    {
32        ans=str2[j-1]+ans;
33        j--;
34        }
35    }
36while(i>0)
37{
38    ans=str1[i-1]+ans;
39    i--;
40}
41while(j>0)
42{
43    ans=str2[j-1]+ans;
44    j--;
45}
46return ans;
47}
48};
49

C# Solution:

1
2csharp
3public class Solution {
4    public string ShortestCommonSupersequence(string str1, string str2) {
5        int len1 = str1.Length;
6        int len2 = str2.Length;
7        int[,] dp = new int[len1+1,len2+1];
8        for(int i=1; i<=len1; i++){
9            for(int j=1; j<=len2; j++){
10                dp[i,j] = (str1[i-1] == str2[j-1]) ? dp[i-1,j-1]+1 : Math.Max(dp[i-1,j], dp[i, j-1]);
11            }
12        }
13        StringBuilder sb = new StringBuilder();
14        while(len1 > 0 && len2 > 0){
15            if(str1[len1-1] == str2[len2-1]){
16                sb.Append(str1[len1-1]);
17                len1--;
18                len2--;
19            }
20            else if(dp[len1-1,len2] > dp[len1,len2-1]){
21                sb.Append(str1[len1-1]);
22                len1--;
23            }
24            else{
25                sb.Append(str2[len2-1]);
26                len2--;
27            }
28        }
29        while(len1 > 0){
30            sb.Append(str1[len1-1]);
31            len1--;
32        }
33        while(len2 > 0){
34            sb.Append(str2[len2-1]);
35            len2--;
36        }
37        return new string(sb.ToString().Reverse().ToArray());
38    }
39}

Time and Space complexity

Time complexity: The time complexity is O(m*n), where m and n are the lengths of the given strings. This is because we iterate over each character of both strings to create the dp table and later to construct the shortest common supersequence.

Space complexity: The space complexity is also O(m*n), because we create a 2-dimensional dp array to store the longest common subsequence information for all pairs of prefixes of both strings.

Where m is the length of string str1 and n is the length of string str2.# Clojure Solution:

1
2clojure 
3(defn build-dp 
4  [str1 str2]
5  (let [m (count str1) 
6        n (count str2) 
7        dp (atom (vec (repeat (inc m) (vec (repeat (inc n) 0)))))]
8
9    (doseq [i (range 1 (inc m))] 
10      (doseq [j (range 1 (inc n))] 
11        (if (= (nth str1 (dec i)) (nth str2 (dec j))) 
12          (swap! dp assoc i (assoc (nth @dp i) j (inc (get-in @dp [(dec i) (dec j)])))) 
13          (swap! dp assoc i (assoc (nth @dp i) j (max (get-in @dp [(dec i) j]) (get-in @dp [i (dec j)])))))))
14
15    @dp))
16
17(defn shortest-common-supersequence 
18  [str1 str2]
19  (let [m (count str1) 
20        n (count str2) 
21        dp (build-dp str1 str2) 
22        ans (atom "")]
23
24    (loop [i m j n]
25      (when (not (and (zero? i) (zero? j))) 
26        (if (= (get-in dp [i j]) (get-in dp [(dec i) (dec j)])) 
27          (do 
28            (swap! ans str (str (nth str1 (dec i)))) 
29            (recur (dec i) j)) 
30          (if (= (get-in dp [i j]) (get-in dp [i (dec j)])) 
31            (do 
32              (swap! ans str (str (nth str2 (dec j)))) 
33              (recur i (dec j))) 
34            (do 
35              (swap! ans str (str (nth str1 (dec i)))) 
36              (recur (dec i) (dec j)))))))
37
38    @ans))
39

The Clojure solution maintains the same overall structure as the solutions provided in other languages. It uses atoms for mutation within a single threaded context, and it uses the Clojure loop/recur special form for efficient tail recursion. Like other solutions, the main work is divided into the creation of a dynamic programming table and the construction of the shortest common supersequence.

Time complexity: O(m*n), where m and n are the lengths of the given strings. It iterates over each character of both strings to create the dp table and later to construct the shortest common supersequence.

Space complexity: O(m*n), because a 2-dimensional dp array is created to store the information for all pairs of prefixes of both strings.

Overall, the Clojure solution is a direct translation of the approach used in Python, Java, JavaScript, C++ and C#. It demonstrates that the dynamic programming approach to solving this problem can be effectively implemented in a functional programming language.