LeetCode 1092. 最短公共超序列

Categories:

题目描述
思路分析
1. 解法一：LCS + 反向构造（推荐）
相似题目

题目描述

✅ 1092. 最短公共超序列

思路分析

解法一：LCS + 反向构造（推荐）

核心思路：

先求出两个字符串的最长公共子序列长度表。

从末尾回溯，根据 DP 决策合并两串。

公共字符只取一次，其余字符按顺序加入。

复杂度分析：

时间复杂度：O(m * n)，其中 m、n 表示字符串长度。

空间复杂度：O(m * n)，用于 DP 表。

class Solution {
    public 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]);
                }
            }
        }

        StringBuilder builder = new StringBuilder();
        int i = m;
        int j = n;
        while (i > 0 || j > 0) {
            if (i == 0) {
                builder.append(str2.charAt(j - 1));
                j--;
            } else if (j == 0) {
                builder.append(str1.charAt(i - 1));
                i--;
            } else if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                builder.append(str1.charAt(i - 1));
                i--;
                j--;
            } else if (dp[i - 1][j] >= dp[i][j - 1]) {
                builder.append(str1.charAt(i - 1));
                i--;
            } else {
                builder.append(str2.charAt(j - 1));
                j--;
            }
        }

        return builder.reverse().toString();
    }
}

func shortestCommonSupersequence(str1 string, str2 string) string {
	m, n := len(str1), len(str2)
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}

	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if str1[i-1] == str2[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				if dp[i-1][j] > dp[i][j-1] {
					dp[i][j] = dp[i-1][j]
				} else {
					dp[i][j] = dp[i][j-1]
				}
			}
		}
	}

	res := make([]byte, 0, m+n)
	i, j := m, n
	for i > 0 || j > 0 {
		if i == 0 {
			res = append(res, str2[j-1])
			j--
		} else if j == 0 {
			res = append(res, str1[i-1])
			i--
		} else if str1[i-1] == str2[j-1] {
			res = append(res, str1[i-1])
			i--
			j--
		} else if dp[i-1][j] >= dp[i][j-1] {
			res = append(res, str1[i-1])
			i--
		} else {
			res = append(res, str2[j-1])
			j--
		}
	}

	for l, r := 0, len(res)-1; l < r; l, r = l+1, r-1 {
		res[l], res[r] = res[r], res[l]
	}

	return string(res)
}

相似题目

题目	难度	考察点
1143. 最长公共子序列	中等	动态规划
583. 两个字符串的删除操作	中等	动态规划
72. 编辑距离	困难	动态规划
712. 两个字符串的最小 ASCII 删除和	中等	动态规划
392. 判断子序列	简单	双指针

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/43827621