最短公共超序列

/*
 * 思路: 这个解法与上一个类似，但是我们利用Java的Stream API来处理字符串的拼接部分。
 * 同样地，我们先用动态规划求出最短公共超序列的长度表，然后反向构建结果字符串。
 */
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class ShortestCommonSupersequenceStream {
    public String shortestCommonSupersequence(String str1, String str2) {
        int m = str1.length();
        int n = str2.length();
        int[][] dp = new int[m + 1][n + 1];

        // 初始化 dp 数组
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0) {
                    dp[i][j] = j;
                } else if (j == 0) {
                    dp[i][j] = i;
                } else if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
                }
            }
        }

        // 使用 Stream 反向构建结果字符串
        String result = IntStream.iterate(m + n - 1, i -> i >= 0, i -> i - 1)
                .mapToObj(i -> new Object() {
                    int index = i;
                    char ch = (index >= m) ? str2.charAt(index - m) : str1.charAt(index);
                })
                .filter(obj -> {
                    if (obj.index >= m || obj.index >= n) return true;
                    if (str1.charAt(obj.index) == str2.charAt(obj.index)) return true;
                    return dp[m - obj.index - 1][n - obj.index - 1] + 1 == dp[m - obj.index][n - obj.index];
                })
                .map(obj -> String.valueOf(obj.ch))
                .collect(Collectors.joining());

        return result;
    }
}