最短公共超序列【LC1092】
给出两个字符串
str1和str2，返回同时以str1和str2作为子序列的最短字符串。如果答案不止一个，则可以返回满足条件的任意一个答案。（如果从字符串 T 中删除一些字符（也可能不删除，并且选出的这些字符可以位于 T 中的 任意位置），可以得到字符串 S，那么 S 就是 T 的子序列）
小难 看到困难题虽然有点思路 但是有不愿继续尝试的畏难感 主要是怕浪费了时间还做不出来
- 思路
- 首先两个字符串的最短公共超序列的结果肯定是两个子字符串的最长公共子序列+两者特有的部分组成；
class Solution { public String shortestCommonSupersequence(String str1, String str2) { int n = str1.length(), m = str2.length(); str1 = " " + str1; str2 = " " + str2; char[] s1 = str1.toCharArray(), s2 = str2.toCharArray(); int[][] f = new int[n + 10][m + 10]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (s1[i] == s2[j]) f[i][j] = f[i - 1][j - 1] + 1; else f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]); } } StringBuilder sb = new StringBuilder(); int i = n, j = m; while (i > 0 || j > 0) { if (i == 0) sb.append(s2[j--]); else if (j == 0) sb.append(s1[i--]); else { if (s1[i] == s2[j]) { sb.append(s1[i]); i--; j--; } else if (f[i][j] == f[i - 1][j]) { sb.append(s1[i--]); } else { sb.append(s2[j--]); } } } return sb.reverse().toString(); } } 作者：宫水三叶 链接：https://leetcode.cn/problems/shortest-common-supersequence/solutions/1825289/by-ac_oier-s346/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
