1
class Solution {
2
  string LCS(string str1, string str2, int m, int n) {
3
    int t[m + 1][n + 1];
4
    string ans = "";
5
    for (int i = 0; i < m + 1; ++i) {
6
      for (int j = 0; j < n + 1; ++j) {
7
        if (i == 0 || j == 0) t[i][j] = 0;
8
      }
9
    }
10

11
    for (int i = 1; i < m + 1; ++i) {
12
      for (int j = 1; j < n + 1; ++j) {
13
        if (str1[i - 1] == str2[j - 1])
14
          t[i][j] = 1 + t[i - 1][j - 1];
15
        else
16
          t[i][j] = max(t[i - 1][j], t[i][j - 1]);
17
      }
18
    }
19
    int i = m, j = n;
20
    while (i > 0 && j > 0) {
21
      if (str1[i - 1] == str2[j - 1]) {
22
        ans.push_back(str1[i - 1]);
23
        --i;
24
        --j;
25
      }
26

27
      else if (t[i][j - 1] > t[i - 1][j]) {
28
        ans.push_back(str2[j - 1]);
29
        --j;
30
      }
31

32
      else {
33
        ans.push_back(str1[i - 1]);
34
        --i;
35
      }
36
    }
37
    while (i > 0) {
38
      ans.push_back(str1[i - 1]);
39
      --i;
40
    }
41
    while (j > 0) {
42
      ans.push_back(str2[j - 1]);
43
      --j;
44
    }
45
    reverse(ans.begin(), ans.end());
46
    return ans;
47
  }
48

49
 public:
50
  string shortestCommonSupersequence(string str1, string str2) {
51
    int m = str1.length();
52
    int n = str2.length();
53

54
    return LCS(str1, str2, m, n);
55
  }
56
};