The shortest common supersequence (SCS) of two sequences $X$ and $Y$ is the shortest sequence which has $X$ and $Y$ as subsequences.

In other words assume we’re given two strings str1 and str2, find the shortest string that has both str1 and str2 as subsequences.

This is a problem closely related to the longest common subsequence problem.

Example

1
2
3
4
5

Input:   str1 = "geek",  str2 = "eke"
Output: "geeke"

Input:   str1 = "AGGTAB",  str2 = "GXTXAYB"
Output:  "AGXGTXAYB"

References

Implementations

  • 1

    # TODO: Implement in Python

  • 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

    const string1 = 'AGGTAB';
const string2 = 'GXTXAYB';
const m = string1.length;
const n = string2.length;
const A = new Array(m + 1);
for (let i = 0; i < m + 1; i++) {
  A[i] = new Array(n + 1);
}

let i;
let j;

// Fill memo table in bottom up manner
for (i = 0; i <= m; i++) {
  for (j = 0; j <= n; j++) {
    if (i === 0) {
      A[i][j] = j;
    } else if (j === 0) {
      A[i][j] = i;
    } else if (string1[i - 1] === string2[j - 1]) {

      A[i][j] = A[i - 1][j - 1] + 1;

    } else {

      if (A[i - 1][j] < A[i][j - 1]) {
        A[i][j] = 1 + A[i - 1][j];
      } else {
        A[i][j] = 1 + A[i][j - 1];
      }

    }
    
  }
}

console.log(`Shortest Common Supersequence is ${A[m][n]}`);