Java代码实现 Java代码实现以下功能 给你两个字符串 str1 和 str2返回同时以 str1 和 str2 作为 子序列 的最短字符串。如果答案不止一个则可以返回满足条件的 任意一个 答案。如果从字符串 t 中删除一些字符也可能不删除可以得到字符串 s 那么 s 就是 t 的一个子序列。

public class ShortestCommonSupersequence { public static String shortestCommonSupersequence(String str1, String str2) { int m = str1.length(); int n = str2.length(); int[][] dp = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (str1.charAt(i - 1) == str2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } int i = m, j = n; StringBuilder sb = new StringBuilder(); while (i > 0 && j > 0) { if (str1.charAt(i - 1) == str2.charAt(j - 1)) { sb.append(str1.charAt(i - 1)); i--; j--; } else if (dp[i - 1][j] > dp[i][j - 1]) { sb.append(str1.charAt(i - 1)); i--; } else { sb.append(str2.charAt(j - 1)); j--; } } while (i > 0) { sb.append(str1.charAt(i - 1)); i--; } while (j > 0) { sb.append(str2.charAt(j - 1)); j--; } return sb.reverse().toString(); }