将一个字符串与另一个字符串交错所需的最小子序列数

Question

我在力扣上看到了原题Minimum of subsequences required to convert one string to another, and it's very similar to this quesion 1055. Shortest Way to Form String

描述：

给定两个字符串 source 和 target，return source 的最小子序列数，使得它们的 concatenation 等于 target。如果任务不可能，return-1.

示例 1：

输入：源=“abc”，目标=“abcbc”

输出：2

说明：目标“abcbc”可以由源“abc”的子序列“abc”和“bc”组成。

假设s'是source的子序列，所以本题就是求s'_1s'_2...s'_k组成target。我的问题是如何找到 interleave 一个字符串到另一个字符串所需的最小子序列数。

例如：

输入：源=“adbsc”，目标=“addsbc”

输出：2

解释：

step1: s'1 = adbc, then target' = ds
step2: s'2 = ds, then target' = ""

不知道能不能把source和target'的最长公共子序列去掉，形成t'，一直重复到t' = "" ].

这是我的代码：

class Solution:
    def shortestWay(self, s: str, t: str) -> int:

        def lcs(s: str, t: str) -> str:
            m, n = len(s), len(t)
            dp = [[0] * (n + 1) for _ in range(m + 1)]
            for i in range(1, m + 1):
                for j in range(1, n + 1):
                    if s[i-1] == t[j-1]:
                        dp[i][j] = dp[i-1][j-1] + 1
                    else:
                        dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            choose = [False] * n
            i, j = m, n
            while i + j != 0:
                if s[i-1] == t[j-1]:
                    choose[j-1] = True
                    i, j = i - 1, j - 1
                elif dp[i][j] == dp[i-1][j]:
                    i -= 1
                elif dp[i][j] == dp[i][j-1]:
                    j -= 1
            print(f'lcs({s}, {t}) is', ''.join(t[i] for i, v in enumerate(choose) if v))
            return ''.join(t[i] for i, v in enumerate(choose) if not v)
        ans = 0
        while t:
            ans += 1
            t1 = lcs(s, t)
            print(repr(t1))
            if t1 == t:
                return -1
            t = t1
        return ans
"""
lcs(adbsc, addsbc) is adbc
'ds'
lcs(adbsc, ds) is ds
''
"""

有谁能帮我解决proof/solve这个问题，谢谢！

Answer 1

你为第二个例子所做的工作（来源=“abc”，目标=“abcbc”）对我来说没有意义。您的算法思想（反复从目标中移除 LCS）产生了一个最优解——您只需要证明没有其他解可以更好。

校样草图

考虑包含 OPT 段的最佳解决方案。如果它等于您的算法的解决方案，那么我们就完成了；否则，它必须由一定数量的公共子序列片段组成，其中第一个 k（可能 k=0）与您的算法产生的片段匹配，然后是严格短于您的算法的第（k+1）个片段第 (k+1) 个段（因为您的算法总是选择在每个阶段添加的最长可能段），然后是一些（可能为零）剩余段。

注意，如果字符串 S 的某个子序列等于字符串 T，那么对于 T 的任何给定 后缀，我们当然可以找到 S 的子序列等于它-- 我们需要做的就是从子序列中删除一些初始字符。

因此，回到我们最初的问题：可以修剪剩余片段的一些初始部分（可能涉及多个片段）以生成一个片段列表，当附加到由生成的前 k+1 个片段时您的算法给出了一个解决方案：

同意算法解的前 k+1 段，并且

段数不比 OPT 差。

我们开始的最佳解决方案与您的算法在前 k 段上的解决方案一致；这个新的最佳解决方案至少同意一个细分市场。如果新的解还不完全等于你的算法的解，那么可以重复分析，产生一个至少在前 k+2 段上与其一致的新解。可以重复此操作，直到我们最终生成与您的算法解决方案完全一致且长度为 OPT 的解决方案。由于我们没有对输入实例做出任何假设，这证明您的算法在每个输入实例上都产生了最优解。

将一个字符串与另一个字符串交错所需的最小子序列数

Minimum number of subsequences required to interleave one string to another

string

algorithm

subsequence

校样草图