LCS

最长公共子序列

AcWing 897. 最长公共子序列

给定两个长度分别为 NN 和 MM 的字符串 AA 和 BB，求既是 AA 的子序列又是 BB 的子序列的字符串长度最长是多少。
输入格式
第一行包含两个整数 NN 和 MM。
第二行包含一个长度为 NN 的字符串，表示字符串 AA。
第三行包含一个长度为 MM 的字符串，表示字符串 BB。
字符串均由小写字母构成。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N,M≤10001≤N,M≤1000
输入样例：
4 5
acbd
abedc
输出样例：
3

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        String s1 = sc.next(), s2 = sc.next();
        int[][] f = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            char c1 = s1.charAt(i - 1);
            for (int j = 1; j <= m; j++) {
                char c2 = s2.charAt(j - 1);
                f[i][j] = Math.max(f[i][j-1], f[i-1][j]);
                if (c1 == c2)
                    f[i][j] = Math.max(f[i][j], f[i-1][j-1] + 1);
            }
        }
        System.out.println(f[n][m]);
    }
}

1092. 最短公共超序列

给出两个字符串 str1 和 str2，返回同时以 str1 和 str2 作为子序列的最短字符串。如果答案不止一个，则可以返回满足条件的任意一个答案。
（如果从字符串 T 中删除一些字符（也可能不删除，并且选出的这些字符可以位于 T 中的 任意位置），可以得到字符串 S，那么 S 就是 T 的子序列）

示例：
输入：str1 = “abac”, str2 = “cab” 输出：“cabac” 解释： str1 = “abac” 是 “cabac” 的一个子串，因为我们可以删去 “cabac” 的第一个 “c”得到 “abac”。 str2 = “cab” 是 “cabac” 的一个子串，因为我们可以删去 “cabac” 末尾的 “ac” 得到 “cab”。 最终我们给出的答案是满足上述属性的最短字符串。

提示：

1. 1 <= str1.length, str2.length <= 1000
2. str1 和 str2 都由小写英文字母组成。

思路：
涉及了LCS求具体方案

class Solution {
    public String shortestCommonSupersequence(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        int[][] f = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            char c1 = s1.charAt(i - 1);
            for (int j = 1; j <= m; j++) {
                char c2 = s2.charAt(j - 1);
                if (c1 == c2)
                    f[i][j] = f[i - 1][j - 1] + 1;
                f[i][j] = Math.max(f[i][j], Math.max(f[i - 1][j], f[i][j - 1]));
            }
        }
        int x = n, y = m;
        StringBuilder sb = new StringBuilder();
        while (x > 0 || y > 0) {
            if (x == 0) {
                sb.append(s2.charAt(y - 1));
                y--;
            } else if (y == 0) {
                sb.append(s1.charAt(x - 1));
                x--;
            } else {
                if (s1.charAt(x - 1) == s2.charAt(y - 1)) {
                    sb.append(s1.charAt(x - 1));
                    x--;
                    y--;
                } else {
                    if (f[x][y - 1] == f[x][y]) {
                        sb.append(s2.charAt(y - 1));
                        y--;
                    } else {
                        sb.append(s1.charAt(x - 1));
                        x--;
                    }
                }
            }
        }
        return sb.reverse().toString();
    }
}