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