Dynamic Programming - Shortest Common Supersequence

Dynamic ProgrammingShortest Common Supersequence

Fork

Fullscreen

JavaScript

C++

Java

Building

Play

0 / 1

Speed

README.md

code.js

1
4
5
6
7
8
9
10
11
12
13
14
25
26
27
28
29
30
31
32
33
34
35
36
37
45
46
47
48
53
54
60
61
62
63
64
65
// import visualization libraries {...}
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);
}
// define tracer variables {...}
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]) {
      // visualize {...}
      A[i][j] = A[i - 1][j - 1] + 1;
      // visualize {...}
    } else {
      // visualize {...}
      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];
      }
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Contributed by

archie94

64json

Yee172

Delete File